358. Rearrange String k Distance Apart

This is similar idea to the count sort. First of all, we use hash table to mapping the letter and their appearance times in the input string. And then we want to reorder the string by place k different letters in a row. How can we achieve that? We want to place the letter that has most appearance first. Why? If you place the least appearance first, then you'll be ending up having most appearance letters only and not being able to make k different letters in a row early on. So we think of maximum heap for help. The maximum heap honors the appearance time. Once we place a letter, we need to remove the letter from the heap because it could be still the letter with most appearance but we can't place it until we've place k letters. On the other hand, we still need to cache the removed letters if they still have one more appearance. Once we finish placing k different letters, we push the cached letters back to the heap. Now, the question is in what situation we can't rearrange the string? When we are rearranging k letters, as long as the heap has more than k letters we are find. However, if the heap becomes empty (note we are removing letters when we've placed them), it means we can't make k different letters in a row. At this moment, we know that this string can't be rearranged.

1:  class Solution {  
2:  public:  
3:    string rearrangeString(string str, int k) {  
4:      if (k == 0) return str;  
5:      int l = str.size();  
6:      string res;  
7:      unordered_map<char, int> mp;  
8:      priority_queue<pair<int, char>> pq;  
9:      for (int i = 0; i < l; i++) mp[str[i]]++;  
10:      for (auto it : mp) pq.push(make_pair(it.second, it.first));  
11:      while (!pq.empty()) {  
12:        vector<pair<int, char>> cache;  
13:        int c = min(l, k);  
14:        for (int i = 0; i < c; i++) {  
15:          if (pq.empty()) return "";  
16:          pair<int, char> tmp = pq.top();  
17:          pq.pop();  
18:          res += tmp.second;  
19:          if (--tmp.first > 0) cache.push_back(tmp);  
20:          l--;  
21:        }  
22:        for (auto i : cache) pq.push(i);  
23:      }  
24:      return res;  
25:    }  
26:  };