358. Rearrange String k Distance Apart

max heap+greedy O(nlog26) time O(26) space
跟621. Task Scheduler很像
按照字符频数由大到小放到k个slot里，用一个最大堆来维护字符顺序（频数高的在前，相同频数的ASCII码小的在前），每次从最大堆里pop出k个不同字符缓存起来并更新每个字符的频数（减1），如果字符频数不为0则加入缓存，则最后统一从缓存里加回最大堆，如果一旦中间过程中最大堆为空了而字符还没填满，说明有的字符频数过高，无法满足相同字符间距至少为k的要求，直接返回空串

class Solution {
public:
    string rearrangeString(string s, int k) {
        if (k == 0) return s;
        int f[26] = {0};
        for (char c : s) {
            ++f[c - 'a'];
        }
        auto cmp = [&f](int a, int b) { return f[a] == f[b] ? a > b : f[a] < f[b]; }; // 频数高的优先，相同频数的ASCII码小的优先
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
        for (int i = 0; i < 26; ++i) {
            if (f[i] > 0) {
                q.push(i);
            }
        }
        int n = s.length();
        string res;
        while (!q.empty()) {
            vector<int> v; // 每次缓存k个字符
            int sz = min(k, n); // 这里由于要对n进行更新所以要提前判断还需要append几个字符
            for (int i = 0; i < sz; ++i) {
                if (q.empty()) return ""; // q为空，说明有字符过多，不满足相同字符间隔至少为k的要求
                int x = q.top(); q.pop();
                res += 'a' + x;
                if (--f[x] > 0) { // 如果放完当前字符还有剩余，则稍后放回堆
                    v.push_back(x);
                }
                --n; // 每append一个字符，更新需求n
            }
            for (int x : v) { // 最后统一从缓存加回最大堆
                q.push(x);
            }
        }
        return res;
    }
};

用类似767. Reorganize String的处理方法

class Solution {
public:
    string rearrangeString(string s, int k) {
        if (k == 0) return s;
        int f[26] = {0};
        iota(f, f + 26, 0);
        for (char c : s) {
            f[c - 'a'] += 100;
        }
        priority_queue<int> q;
        for (int i = 0; i < 26; ++i) {
            if (f[i] > 99) {
                q.push(f[i]);
            }
        }
        int n = s.length();
        string res;
        while (!q.empty()) {
            vector<int> v; // 每次缓存k个字符
            int sz = min(k, n); // 这里由于要对n进行更新所以要提前判断还需要append几个字符
            for (int i = 0; i < sz; ++i) {
                if (q.empty()) return ""; // q为空，说明有字符过多，不满足相同字符间隔至少为k的要求
                int x = q.top(); q.pop();
                res += 'a' + x % 100;
                x -= 100;
                if (x > 99) { // 如果放完当前字符还有剩余，则稍后放回堆
                    v.push_back(x);
                }
                --n; // 每append一个字符，更新需求n
            }
            for (int x : v) { // 最后统一从缓存加回最大堆
                q.push(x);
            }
        }
        return res;
    }
};