358. Rearrange String k Distance Apart【discuss】

https://leetcode.com/problems/rearrange-string-k-distance-apart/

https://leetcode.com/discuss/108174/c-unordered_map-priority_queue-solution-using-cache
Discuss的代码，写的很完美啊：
用一个cache去存储需要间隔k的char。在下一次的for循环里再放入res。

class Solution {
public:
    string rearrangeString(string str, int k) {
        if(k == 0) return str;
        int length = (int)str.size(); 

        string res;
        unordered_map<char, int> dict;
        priority_queue<pair<int, char>> pq;

        for(char ch : str) dict[ch]++;
        for(auto it = dict.begin(); it != dict.end(); it++){
            pq.push(make_pair(it->second, it->first));
        }

        while(!pq.empty()){
            vector<pair<int, char>> cache; //store used char during one while loop
            int count = min(k, length); //count: how many steps in a while loop
            for(int i = 0; i < count; i++){
                if(pq.empty()) return "";
                auto tmp = pq.top();
                pq.pop();
                res.push_back(tmp.second);
                if(--tmp.first > 0) cache.push_back(tmp);
                length--;
            }
            for(auto p : cache) pq.push(p);
        }
        return res;
    }
};