题解 | #小红的字符串构造#

• 强调这题没有对数量作要求，比如abbcde，我们取下一个字母，即bccdea满足题意。

• 我们考虑用usechar存储字符集，把字符集存到vector数组方便管理。 随后我们考虑用lower_bound找到字符串中每一个字符s[i]在distinct_chars的位置，仅需让迭代器+1，就得到了下一个字母，并输出。

• 如果是最后一个字母（判断方式为it == distinct_chars.end() - 1），只需让迭代器取最开头的一个就行。

• sort是必要的，否则lower_bound无法使用（lower_bound适用于有序）。

• 排序的时间复杂度近乎不计，总体而言时间复杂度O（n）

#include <bits/stdc++.h>
using namespace std;

unordered_set<char> usechar;

int main()
{
    string s; cin >> s;
    for (auto ele:s){
        usechar.insert(ele);
    }

    if (usechar.size() == 1)
    {
        cout << -1 << endl;
        return 0;
    }

    vector<char> distinct_chars(usechar.begin(), usechar.end());
    int n = distinct_chars.size();
    sort(distinct_chars.begin(),distinct_chars.end()); //方便使用lower_bound

    for (int i = 0; i < s.size(); ++i)
    {
        char c = s[i];
        auto it = lower_bound(distinct_chars.begin(),distinct_chars.end(),c);
        if (it == distinct_chars.end() - 1) it = distinct_chars.begin();
        else it = it + 1;
        cout << *it ;
    }
    return 0;
}