摘要

這道題的核心是：把字符串里的字符重新排一下順序，讓相同字符之間至少隔開 k 個位置。如果做不到，就返回空串。看上去像“排座位”，其實是一道標準的“貪心 + 堆 + 冷卻隊列”題。本文用 Swift 寫出一份可直接運行的 Demo，順便把實現細節和常見坑講清楚。

描述

給定一個字符串 s 和整數 k，要求把 s 里的字符重新排列，使得任意兩個相同字符在新字符串中的位置至少相隔 k。

• 如果存在這樣的重排，返回重排后的字符串。
• 如果不存在，返回 ""。

直覺：頻率高的字符更“難安置”，理應優先被安排；但又不能連續塞，必須“冷卻”至少 k-1 個位置。于是我們需要：

1. 一個**最大堆（優先隊列）**按剩余次數挑選字符。
2. 一個冷卻隊列存放剛剛用過的字符，等走過 k 步再重新投入堆。

解決方法

思路分三步：

1. 統計每個字符的出現次數。

2. 用最大堆按“剩余次數”挑一個當前最應該放的字符。

3. 將每輪最多取 k 個不同字符依次放入結果，同時把它們的剩余次數減一并放入“等待區”。當這輪結束，再把等待區里還剩次數的字符放回堆，進入下一輪。

   • 如果某輪拿不到足夠的不同字符，但還有字符沒用完，說明無法滿足間隔要求，直接返回 ""。

這個分輪的方式，簡單直觀，也好寫對。

分析問題和解決代碼

下面是完整的 Swift 實現，包含一個通用的最大堆（優先隊列）實現、解題函數，以及可運行的測試 Demo。

import Foundation// MARK: - Generic Max Heap
public struct PriorityQueue<Element> {private var elements: [Element] = []private let areSorted: (Element, Element) -> Bool  // max-heap: return lhs > rhspublic init(sort: @escaping (Element, Element) -> Bool) {self.areSorted = sort}public var isEmpty: Bool { elements.isEmpty }public var count: Int { elements.count }public mutating func push(_ value: Element) {elements.append(value)siftUp(from: elements.count - 1)}public mutating func pop() -> Element? {guard !elements.isEmpty else { return nil }elements.swapAt(0, elements.count - 1)let item = elements.removeLast()siftDown(from: 0)return item}public func peek() -> Element? {elements.first}private mutating func siftUp(from index: Int) {var child = indexvar parent = (child - 1) / 2while child > 0 && areSorted(elements[child], elements[parent]) {elements.swapAt(child, parent)child = parentparent = (child - 1) / 2}}private mutating func siftDown(from index: Int) {var parent = indexwhile true {let left = parent * 2 + 1let right = left + 1var candidate = parentif left < elements.count && areSorted(elements[left], elements[candidate]) {candidate = left}if right < elements.count && areSorted(elements[right], elements[candidate]) {candidate = right}if candidate == parent { return }elements.swapAt(parent, candidate)parent = candidate}}
}// MARK: - Solution
class Solution {/// Rearrange string so that same chars are at least k distance apart./// - Returns: rearranged string or "" if impossiblefunc rearrangeString(_ s: String, _ k: Int) -> String {// 快速返回：k <= 1 不需要限制if k <= 1 { return s }if s.isEmpty { return "" }// 1) 統計頻率var freq = [Character: Int]()for ch in s {freq[ch, default: 0] += 1}// 2) 最大堆，按剩余次數排序（次數相同可按字母排序，方便穩定）// 元組：(char, count)var maxHeap = PriorityQueue<(Character, Int)>(sort: { (a, b) inif a.1 == b.1 {return a.0 < b.0  // 次數相等時，字典序更小的優先（不必須，但穩定）}return a.1 > b.1})for (ch, c) in freq {maxHeap.push((ch, c))}// 3) 分輪放置，每輪最多放 k 個不同字符var result: [Character] = []// 臨時存放本輪用過的字符（減1后如果還有余量，等輪末再壓回堆）while !maxHeap.isEmpty {var usedInThisRound: [(Character, Int)] = []var take = min(k, s.count - result.count) // 剩余位數可能不足 kfor _ in 0..<take {guard let (ch, c) = maxHeap.pop() else {// 堆空但還沒填滿（說明還有待放字符被卡住），失敗// 注意：只有當結果未完成且堆空時，才是失敗return ""}result.append(ch)if c - 1 > 0 {usedInThisRound.append((ch, c - 1))}// 若已經填滿，提前結束if result.count == s.count { break }}// 輪末：把本輪用過仍有余量的字符壓回堆for item in usedInThisRound {maxHeap.push(item)}// 如果堆仍有元素，但是這一輪沒湊夠 k 個且結果還沒填滿，說明必須留空位才能滿足距離要求，但字符串不允許空位 => 不可能if !maxHeap.isEmpty && result.count < s.count && usedInThisRound.count < k {// 這個判斷等價：本輪拿的不同字符數 < k，但后面還有字符沒安排// 說明“冷卻距離”要求擋住了return ""}}return String(result)}
}// MARK: - Demo (Runnable)
func demo() {let sol = Solution()let cases: [(String, Int)] = [("aabbcc", 3),     // 可行，典型示例("aaabc", 3),      // 不可行，返回 ""("aaadbbcc", 2),   // 可行("a", 2),          // 只有一個字符，k>1 也可行（本身就滿足）("", 2),           // 空串("aa", 1),         // k=1 總是原樣即可("aa", 2),         // 需要至少間隔 2，兩個 a 無法滿足 => ""]for (s, k) in cases {let ans = sol.rearrangeString(s, k)print("Input: s=\(s), k=\(k) -> Output: \(ans.isEmpty ? "\"\"" : ans)")}
}// Run demo
demo()

代碼要點詳解

1. 最大堆設計

   • 我們用泛型 PriorityQueue，構造時傳 sort 比較函數，讓它成為“最大堆”。
   • 堆里的元素是 (Character, Int)，其中 Int 是剩余頻次，按頻次降序；為了穩定性，頻次相同按字符字典序小的優先（不必須，僅讓結果可預期一點）。

2. 分輪取 k 個不同字符

   • 每一輪最多取 k 個不同字符，確保相同字符之間天然相隔至少 k。
   • 本輪用過的字符，頻次減一后暫存到 usedInThisRound，等這一輪結束再放回堆，避免本輪再次被取到。

3. 失敗條件

   • 如果堆提前空了但還沒填滿字符串，說明被“冷卻”規則卡住了，不可行。
   • 或者本輪沒拿滿 k 個（意味著后面位置距離不夠了）且堆里還有字符，也是不可能的情況，返回空串。

4. 為什么不是用“時間戳冷卻”

   • 另一種寫法是給每個字符打“readyTime”，當 i >= readyTime 才能重新入堆。這也行，但分輪更直觀：一輪拿 k 個不同字符，本輪結束再回堆，自然保證間隔。

示例測試和結果

運行上面的 demo()，輸出大致如下（具體順序可能因為同頻字符的 tie-breaker 有細微差別，但滿足約束即可）：

Input: s=aabbcc, k=3 -> Output: abcabc
Input: s=aaabc, k=3 -> Output: ""
Input: s=aaadbbcc, k=2 -> Output: abacabcd
Input: s=a, k=2 -> Output: a
Input: s=, k=2 -> Output: ""
Input: s=aa, k=1 -> Output: aa
Input: s=aa, k=2 -> Output: ""

簡單解釋：

• aabbcc、k=3：可以按 abcabc 擺，符合任意同字母之間至少隔 3。
• aaabc、k=3：a 太多，中間插不進足夠的“墊片”，失敗。
• aaadbbcc、k=2：可以，比如 abacabcd 就行。
• 單字符或 k=1 都是“沒有硬性間隔限制”，基本能過。

時間復雜度

• 設字符串長度為 n，不同字符種類數為 σ（最多 26 個小寫，或 128/256 ASCII）。
• 每個字符都會被插入/彈出堆多次（與它的頻次成正比），堆操作是 O(log σ)。
• 總體復雜度：O(n log σ)。在英文小寫場景基本可視為 O(n)。

空間復雜度

• 頻率表 O(σ)，堆 O(σ)，結果 O(n)。
• 額外空間：O(n + σ)，在字符集有限時接近 O(n)。

總結

這題看似是“重排字符串”，其實就是優先安排最難放的字符，再用冷卻隊列保證間隔。實現上：

• 用最大堆挑剩余次數最多的字符；
• 分輪放置，每輪最多 k 個不同字符，輪末再把有余量的字符放回堆；
• 如果某輪拿不到 k 個，但還有字符沒放完，說明不可能。

這種模式在很多“調度/任務安排”的題里都能復用，比如 CPU 任務調度、訂單/工位分配等。寫成 Swift 后，借助一個干凈的優先隊列模板，整件事就順了。歡迎把這份 Demo 拿去直接跑，也可以按你業務里的字符集和限制微調。