358. Rearrange String k Distance Apart

Given a non-empty stringsand an integerk, rearrange the string such that the same characters are at least distancekfrom 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:

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

Example 2:

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

Example 3:

s = "aaadbbcc", k = 2
Answer: "abacabcd"
Another possible answer is: "abcabcda"
The same letters are at least distance 2 from each other.

S: greedy + heap O(N)

计算每个字母出现的次数，用priority_queue维护以当前出现次数排列的heap。以k个字母为一轮，每次取出当前剩余出现次数最多的char 加入result

因为只有26个小写字母，priority_queue最多有26个元素，插入删除可视为常数，时间复杂度为O(n)

    string rearrangeString(string s, int k) {
        int n = s.size();
        if (n == 0 || k == 0) return s;
        unordered_map<char, int> count;
        priority_queue<pair<int, char>> pq;
        string result = "";
        for (char c : s) count[c]++;
        for (const auto& i : count) pq.push(make_pair(i.second, i.first));
        while (!pq.empty()) {
            vector<pair<int, char>> cache;  //存储此轮使用过的元素
            int size = n - result.size();
            int m = min(size, k);
            for (int i = 0; i < m; ++i) {  //每k个char为一轮
                if (pq.empty()) return "";  //没有不重复的元素了
                pair<int, char> p = pq.top();
                pq.pop();
                result += p.second;
                p.first--;
                if (p.first) cache.push_back(p);
            }
            for (const auto& i : cache) pq.push(i);
        }
        return result;
    }