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

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

示例 1:

输入: S = "aab"
输出: "aba"

示例 2:

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

注意:

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

解答

贪心，使用最大堆维护每个字母出现的次数，每次将出现次数最多的两个字母取出进行拼接。

class Solution {
public:
    string reorganizeString(string S) {
        if(S.size() <= 1)
            return S;
        vector<int> record(26, 0);
        for(auto & c : S)
            record[c - 'a']++;
        // 维护最大堆
        auto cmp = [&](const pair<int, int> &p1, const pair<int, int> &p2){
            return p1.second < p2.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> heap{cmp};
        for(int i = 0; i < 26; i++){
            if(record[i] > 0)
                heap.push({i, record[i]});
        }
        // 出现次数最多的字符不能超过总数一半
        // 加1对奇偶合并处理
        if(heap.top().second > (S.size() + 1) / 2)
            return "";
        
        string result = "";
        while(heap.size() > 1){
            auto p1 = heap.top();
            heap.pop();
            auto p2 = heap.top();
            heap.pop();
            result += (p1.first + 'a');
            result += (p2.first + 'a');
  
            if(--p1.second > 0)
                heap.push(p1);
            if(--p2.second > 0)
                heap.push(p2);

        }
        if(heap.size() > 0)
            result += (heap.top().first + 'a');
        
        return result;
    }
};