1. 题目

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

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

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

示例 2: 输入: S = "aaab" 输出: ""

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reorganize-string 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

这种贪心题找找规律就好了

可以发现，只要能将数量最多的字符隔开就好了。

设数量最多的字符数量为maxV，其他的字符总数量为sum，如果maxV>sum+1就说明无解，否则一定有解。

有解的话构造字符串，一种方式是：

每次将数量最多且与上一次的字符不同的字符加到返回字符串的最后一位

3. 代码

利用优先队列，动态的取出数量最多的字符

利用lambda函数对有限队列进行排序

做的有点麻烦了，可以优化

#define P pair<char,int>
class Solution {
public:
    string reorganizeString(string S) {
        auto cmp = [](const P& a, const P& b){
            if(b.second!=a.second) return a.second<b.second;
            else return a.first<b.first;
        };
        priority_queue<P,vector<P>,decltype(cmp)> que(cmp);
        priority_queue<P,vector<P>,decltype(cmp)> Q(cmp);
        map<char,int> table;
        for(auto &x: S) table[x]++;
        for(auto &x: table) {
            que.push(x);
        }

        int sum = 0,maxV = que.top().second;
        P tmp = que.top();que.pop();
        Q.push(tmp);
        while(!que.empty()){
            sum+=que.top().second;
            Q.push(que.top());
            que.pop();   
        }
        if(sum+1<maxV) return "";


        string res;
        P tmp1,tmp2;
        while(!Q.empty()){
            if(tmp2.second) Q.push(tmp2);
            tmp1 = Q.top();
            Q.pop();
            res+=tmp1.first;
            tmp1.second--;

            if(!Q.empty()){
                tmp2 = Q.top();
                Q.pop();
                res+=tmp2.first;
                tmp2.second--;

                if(tmp1.second) Q.push(tmp1);
            }else if(tmp1.second) Q.push(tmp1);
        }

        return res;
    }
};

4. 知识点

利用lambda函数对priority_queue进行自定义排序时，要借助auto和decltype关键字：

auto cmp = [](const P& a, const P& b){
    if(b.second!=a.second) return a.second<b.second;
    else return a.first<b.first;
};
priority_queue<P,vector<P>,decltype(cmp)> que(cmp);