Leetcode 358: Rearrange String K Distance Apart

 https://leetcode.com/problems/find-latest-group-of-size-m/description/

Notes:

This question is very similar as another question Leetcode 621 (since I solved that question first...)

The basic idea is the same: we need to find the letter with the largest count (m), then for the first (m-1) we have to place (m-1)*k letters (including the letter with the maximum count). 

Then for the last one letter, we do not need to keep it k distance apart from the next one (since there is no next one...). If there is no letter with the tied maximum counting, we just need to add 1 (the letter itself), but if there are n letters with the maximum counting, then the need to add n more letters, to list all the letter with k distance apart.

The overall letters need are (m-1)*k + n. If this value is larger than the size of the string, then there is not enough letters to maintain k distance apart: means that this is impossible. Otherwise, it is okay to form an valid one.

Since this question requests to return one final string, so we can consider to use a priority queue for valid ones: 

1): every time, we pick up one with the largest counting; 

2): and we keep this until we have pop out k different letters. This will form one valid "k-distance" apart substring; 

3): then we need to put the previous pop-out elements back to the priority queue, if their size still larger than 1 after removing 1.

4): repeat this process until there is no element remaining in the queue.

See the code below:

class Solution {
public:
    string rearrangeString(string str, int k) {
        if (k == 0) return str;
        string res;
        int len = (int)str.size(), mx = 0, rep = 0;
        unordered_map<char, int> m;
        priority_queue<pair<int, char>> q;
        for (auto a : str) ++m[a];
        for (auto it = m.begin(); it != m.end(); ++it) {
            q.push({it->second, it->first});
            // find the maximum counting, and the numer of letters having this 
	    if (it->first > mx) {
                mx = it->first;
                rep = 1;
	    } else if (it->first == mx) {
                ++rep;   
            }
        }
        // if need more letters than itself, then cannot construct an valid one
        if((m-1)*k + rep > len) return "";
        while (!q.empty()) {
            vector<pair<int, int>> v;
            int cnt = min(k, len);
            for (int i = 0; i < cnt; ++i) {
                if (q.empty()) return "";
                auto t = q.top(); q.pop();
                res.push_back(t.second);
                if (--t.first > 0) v.push_back(t);
                --len;
            }
            for (auto a : v) q.push(a);
        }
        return res;
    }
};