題目網址：https://leetcode.cn/problems/rearrange-string-k-distance-apart/

題意：給一 string s 和一整數 k, 重新排列 s 使得相同 char 位置間隔距離至少為 k。若無法做到, 則返回 ""。

Solution：

想法：利用 Greedy 和 Heap, 類似 621. Task Scheduler 和 767. Reorganize String, 要相同 char 之間距離為 k, 可想成是若每一輪能取出不同 k 個 char, 則每一輪相同 char 之間距離一定 ≥ k, 要記得考慮不滿 k 個 char 的情況

class Solution {
public:
    string rearrangeString(string s, int k) {
        // 在沒有限制間隔距離的情況下, 直接返回 s
        if (k == 0) {
            return s;
        }

        // 計算 s 中每種 char 的出現次數
        unordered_map<char, int> freq;
        for (const auto& ch : s) {
            ++freq[ch];
        }

        priority_queue<pair<int, char>> q; // max heap
        for (const auto& [ch, num] : freq) {
            q.emplace(num, ch);
        }

        s = "";
        while (!q.empty()) {
            const int m = q.size();

            // q.size() < k 代表此輪為最後一輪
            // 若剩餘 char 的最大出現次數 > 1, 表示最後一輪必定重複
            if (m < k && q.top().first > 1) {
                return "";
            }

            const int cycle = min(k, m); // 可能有不滿 k 個的情況(最後一輪)
            vector<pair<int, char>> tmp;

            // 一次取出 n 個不同種類的 char, 取出後出現次數要 - 1
            for (int i = 0; i < cycle; ++i) {
                const auto [num, ch] = q.top();
                s += ch;
                tmp.emplace_back(num - 1, ch); // 出現次數 - 1
                q.pop();
            }

            // 若取出後的 char 之出現次數 > 0, 則 push 回 q 中
            for (const auto& [num, ch] : tmp) {
                if (num > 0) {
                    q.emplace(num, ch);
                }
            }
        }
        
        return s;
    }
};
  • time：$O(n \cdot log(n))$ ➔ 每次 heap 取出元素後, 需花 $O(log(n))$ 調整 heap, 總共取 n 次
  • space：$O(n)$ ➔ q 中的元素不超過 n