358. Rearrange String k Distance Apart

Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

Example 1:

Input: s = "aabbcc", k = 3
Output: "abcabc" 
Explanation: The same letters are at least distance 3 from each other.

Example 2:

Input: s = "aaabc", k = 3
Output: "" 
Explanation: It is not possible to rearrange the string.

Example 3:

Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least distance 2 from each other.

// Hash table + greedy + heap
string rearrangeString(string s, int k) { // time: O(nlogn); space: O(n)
    if (k == 0) return s;
    string res;
    int len = (int)s.length();
    unordered_map<char, int> m;
    priority_queue<pair<int, char> > q;
    for (auto& a : s) ++m[a];
    for (auto& e : m) q.push({e.second, e.first});
    while (!q.empty()) {
        vector<pair<int, char>> 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;
}

621. Task Scheduler767. Reorganize String