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;
}
}; 