MediumRating 1681
767. Reorganize String
hash-tablestringgreedysortingheap-priority-queuecounting
解題說明
Reorganize String
題目描述：給定一個字串 s，重新排列其中的字元，使得任意兩個相鄰字元都不相同。如果可以實現，回傳任意一種排列結果；否則回傳空字串。
解題思路：使用最大堆（Max Heap）+ 貪心策略：
- 先統計每個字元的出現頻率。若任何字元的頻率超過
(n+1)/2，則無法排列，回傳空字串。 - 建立一個最大堆，按頻率排序。
- 每次從堆中取出頻率最高的兩個字元，分別放入結果字串，然後頻率各減 1 後放回堆中。
- 若堆中只剩一個字元，直接放入結果。
這樣每次都優先使用頻率最高的字元，確保不會有連續相同字元。
C++ 解法
複雜度分析
時間複雜度：O(n log k) — n 為字串長度，k 為不同字元數（最多 26）。每次堆操作 O(log k)，共 O(n) 次。
空間複雜度：O(k) — 堆和頻率陣列的大小，k 最多 26，視為 O(1)。
虛擬碼
1. Count frequency of each character 2. If any frequency > (n+1)/2, return "" 3. Build max heap with (frequency, character) pairs 4. While heap size >= 2: a. Pop top two: (f1, c1) and (f2, c2) b. Append c1 and c2 to result c. Decrement frequencies; push back if > 0 5. If heap has one element left, append it 6. Return result
其他解法
插空法（Interleaving）：按頻率排序所有字元，先填偶數位置（0, 2, 4, ...），再填奇數位置（1, 3, 5, ...）。這保證頻率最高的字元不會相鄰。時間 O(n)，空間 O(n)。比堆的方法更高效且不需要堆的 log 因子。
貪心 + 排序：每次選頻率最高且與前一個不同的字元放入。需要維護排序順序，時間 O(n * 26)。
延伸思考
- 插空法為什麼能保證正確性？它和堆的方法有什麼等價關係？
- 如果要求相鄰字元之間的距離至少為 k（Task Scheduler 問題），該如何擴展？
- 如果字串中有大小寫字母和數字，需要修改什麼？