相同字母至少距离 k

相同字母至少距离k

vector<int> rearrangeBarcodes(vector<int>& barcodes) {
    const int N = barcodes.size();
    unordered_map<int, int> cnt;
    for (int code : barcodes) {
        cnt[code]++;
    }

    auto cmp = [&cnt](int a, int b) { return cnt[a] < cnt[b]; };
    priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
    for (auto &e : cnt) pq.push(e.first);

    vector<int> ans;
    queue<int> freezed;
    while (!pq.empty()) {
        int code = pq.top(); pq.pop();
        ans.push_back(code);
        cnt[code]--;
        
        freezed.push(code);
        if (freezed.size() >= 2) { // 相同项至少距离2
            int released = freezed.front(); freezed.pop();
            if (cnt[released] > 0) pq.push(released);
        }
    }
    return ans;
}

https://leetcode.com/problems/rearrange-string-k-distance-apart/

Given a non-empty string **str **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:
str = "aabbcc", k = 3

Result: "abcabc"

The same letters are at least distance 3 from each other.
Example 2:
str = "aaabc", k = 3 

Answer: ""

It is not possible to rearrange the string.
Example 3:
str = "aaadbbcc", k = 2

Answer: "abacabcd"

Another possible answer is: "abcabcda"

The same letters are at least distance 2 from each other.

class Solution {
public:
    using Pair = pair<char, int>;
    string rearrangeString(string s, int k) {
        // 剩余最多的字母优先
        unordered_map<char, int> cnt;
        for (char c : s) cnt[c]++;
        auto cmp = [](const Pair &a, const Pair &b) {
            return a.second < b.second; // 最大堆
        };
        priority_queue<Pair, vector<Pair>, decltype(cmp)> pq(cmp);
        for (auto &e : cnt) pq.push(e);

        string ans;
        queue<Pair> freezed;
        while (!pq.empty()) {
            auto top = pq.top(); pq.pop();
            ans += top.first;
            top.second--;
            // 每个字母输出后都进freezed队列，包括{c,0}
            freezed.push(top);
            if (freezed.size() >= k) { // 队头解冻回堆
                auto released = freezed.front(); freezed.pop();
                if (released.second > 0) pq.push(released);
            }
        }
        return ans.size() == s.size() ? ans : "";
    }
};

algo-aha

相同字母至少距离k