C++刷LeetCode（767. 重构字符串）【字符串】**

糖逗

题目描述：

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
输出: "aba"
示例 2:

输入: S = "aaab"
输出: ""
注意:

S 只包含小写字母并且长度在[1, 500]区间内。

class Solution {
public:
    string reorganizeString(string S) {
        //1.选取出现最大频次的字符串作为基准字符串
        vector<int> store(26);
        for(auto cha : S)store[cha - 'a']++;
        int len = S.size();
        int max_num = *max_element(store.begin(), store.end());
        int max_index = max_element(store.begin(), store.end()) - store.begin();
        //最大字符的频次超过半数的就直接返回“”表示不能实现
        if(len % 2 == 0 && max_num > len / 2)return "";
        else if(len % 2 != 0 && max_num > (len + 1)/2)return "";
        string res(max_num, max_index + 'a');
        int temp1 = 0;//表示26个字母中的第几个字母
        int temp2 = 1;//表示在temp2位置前插入(位置从0开始)
        while(temp1 < 26){
            if(temp1 == max_index){
                temp1 ++;
                continue;
            }
            while(store[temp1] != 0){
                store[temp1]--;
                res.insert(temp2, 1, 'a' + temp1);
                temp2 = (temp2 + 2) % res.size();//隔一个字符一插入
            }
            temp1++;
        }
        return res;
    }
};

参考链接：https://leetcode-cn.com/problems ... -bi-ji-767-by-ae2a/

糖逗

之后再看一遍