LeetCode 358. K 距离间隔重排字符串（贪心+优先队列）

示例 1：
输入: s = "aabbcc", k = 3
输出: "abcabc" 
解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。

示例 2:
输入: s = "aaabc", k = 3
输出: "" 
解释: 没有办法找到可能的重排结果。

示例 3
输入: s = "aaadbbcc", k = 2
输出: "abacabcd"
解释: 相同的字母在新的字符串中间隔至少 2 个单位距离。

class Solution {
    struct cmp
    {
        bool operator()(pair<char, int>& a, pair<char, int>& b){
            if(a.second == b.second)
                return a.first < b.first;
            return a.second < b.second;//数量多的优先
        }
    };
public:
    string rearrangeString(string s, int k) {
    	if(k <= 1) return s;
        unordered_map<char, int> count;
        for(int i = 0; i < s.size(); i++) 
        	count[s[i]]++;//计数
        priority_queue<pair<char, int>, vector<pair<char,int>>, cmp> q;
        for(auto& c : count)
            q.push(c);//插入优先队列
        string ans;
        while(q.size() >= k)
        {
        	vector<pair<char, int>> temp;
        	int t = k;
        	while(t--)//去除前k个最多的
        	{
        		auto tp = q.top();
        		q.pop();
        		int num = tp.second;
        		char ch = tp.first;
        		ans += ch;
        		num--;
        		if(num != 0)//不为0的先存起来
        			temp.push_back({ch, num});
        	}
        	for(auto& char_num : temp)//再放回队列
        		q.push(char_num);
        }
        while(!q.empty())
        {
            if(q.top().second == 1)
            {
                ans += q.top().first;
                q.pop();
            }
            else//计数不为1的，间距不满足要求
                return "";
        }
        return ans;
    }
};