題目網址：https://leetcode.cn/problems/reorganize-string/

題意：給一 string s, 重新建構 s 使得相鄰的 char 不同。

返回 s 任何可能的排列。若不可行, 則返回 ""。

Solution：

想法：利用 Heap, 若有 char 的出現次數超過 $\dfrac{n+1}{2}$, 則不可能存在相鄰 char 不同的 string

  • 建立 max heap
  • 每次從 heap 中取兩個 top, 保證這兩個 char 必不相同
  • 取出 top 後, 其 count - 1 若 > 0, 將其 push 回 heap 中
  • 跳出 while loop 是因為 pq.size() < 2
    • 若 pq.size() == 1：s 要加上 pq.top()
    • 若 pq.size() == 0：直接返回 s
class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> freq;
        for (const auto& ch : s) {
            ++freq[ch];
        }

        priority_queue<pair<int, char>> pq; // max heap
        const int half = (s.size() + 1) / 2;

        for (const auto& [ch, num] : freq) {
            if (num > half) { // 若超過 (n+1) / 2
                return "";
            }
            pq.emplace(num, ch);
        }

        s = "";
        while (pq.size() >= 2) {
            const auto top1 = pq.top();
            pq.pop();
            const auto top2 = pq.top();
            pq.pop();

            s += top1.second;
            s += top2.second;

            if (--top1.first > 0) {
                pq.emplace(top1);
            }

            if (--top2.first > 0) {
                pq.emplace(top2);
            }
        }

        if (pq.size() > 0) {
            s += pq.top().second;
        }

        return s;
    }
};
  • time：$O(n)$ ➔ $O(n) + O(26 \cdot log(n))$
    • $O(n)$：第一個 for loop, 和 while loop 中重構 s
    • $O(26 \cdot log(n))$：第二個 for loop 最多 insert 26 次
  • space：$O(1)$ ➔ freq 和 pq 最多 26 個元素, 且 s 為 input string, 故只需常數空間