358.rearrange-string-k-distance-apart.md

给你一个非空的字符串  s  和一个整数  k，你要将这个字符串中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离至少为  k。

所有输入的字符串都由小写字母组成，如果找不到距离至少为  k  的重排结果，请返回一个空字符串  ""。

示例 1：

输入: s = "aabbcc", k = 3
输出: "abcabc"
解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。
示例 2:

输入: s = "aaabc", k = 3
输出: ""
解释: 没有办法找到可能的重排结果。
示例 3:

输入: s = "aaadbbcc", k = 2
输出: "abacabcd"
解释: 相同的字母在新的字符串中间隔至少 2 个单位距离。

---

保存一个出现频率的大顶堆，

每一次处理：出堆 k 次，然后将频率减一，入堆

结束条件：出堆不足 k 个，并且有字符出现频率不为 0 堆为空

a : 3 b : 2 c : 2

k = 3

i = 0 -> s.length-1

a : 2 : 0 b : 1 : 1

struct Node {
    char c;
    int limit;

    Node(char _c, int _l) : c(_c), limit(_l) {};

    bool friend operator <(const Node &n1, const Node&n2)  {
        if (n1.limit == n2.limit) return n1.c > n2.c;
        return n1.limit < n2.limit;
    }
};

class Solution {
public:
    string rearrangeString(string s, int k) {
        if (k == 0) return s;
        priority_queue<Node> heap;
        // 统计字符出现次数
        unordered_map<char, int> m;
        for (int i = 0; i < s.length(); i++) {
            if (m.count(s[i]) == 1) m[s[i]]++;
            else m[s[i]] = 1;
        }

        for (auto iter = m.begin(); iter != m.end(); iter++) {
            heap.push({iter->first, iter->second});
        }

        string ans;

        while (!heap.empty()) {
            int i = 0;
            bool ended = true;
            vector<pair<char, int>> lvl;
            for (; i < k && !heap.empty(); i++) {
                auto top = heap.top();
                heap.pop();
                top.limit--;
                if (top.limit > 0) {
                    ans += top.c;
                    lvl.push_back({top.c, top.limit});
                    ended = false;
                } else if (top.limit == 0) {
                    ans += top.c;
                }
            }
            if (i < k && !ended) {
                return "";
            }
            for (auto iter = lvl.begin(); iter != lvl.end(); iter++) {
                heap.push({iter->first, iter->second});
            }
        }
        return ans;
    }
};