[LeetCode] 767. 重构字符串

[Animenzzzz]

题目描述：

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

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

示例 1:

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

示例 2:

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

注意:

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

解题思路：这题使用好的数据结构太重要的。首先使用哈希表，建立好字符和出现次数的映射。然后使用优先队列，存储<int,char>对。这样的话，出现频率最高的字符会被排在队列顶部。然后开始遍历队列，取出前两个分别构建字符串，并且将其出现的次数减1，如果不为0则放回队列中。最后遍历完可能会剩下一个或者0个对，这时有的话加在字符串后就可以了。同时因为之前已经判断过，如果出现次数超过一半就直接返回。。所以最后这一个对肯定不会是大于1的出现次数。

C++解题：

class Solution {
public:
    string reorganizeString(string S) {
        string res;
        unordered_map<char,int> map;
        priority_queue<pair<int,char>> qq;
        for(char cc : S) map[cc]++;
        for(auto a:map){
            if(a.second > (S.size()+1)/2) return "";
            qq.push({a.second,a.first});
        }
        while(qq.size()>=2){
            auto a1 = qq.top();qq.pop();
            auto a2 = qq.top();qq.pop();
            res.push_back(a1.second);
            res.push_back(a2.second);
            if(--a1.first > 0) qq.push(a1);
            if(--a2.first > 0) qq.push(a2);
        }
        if(qq.size()) res.push_back(qq.top().second);
        return res;
    }
};