題目與情境
每次相鄰交換成本為 1，字元可能重複，也可能因多個奇數頻次而無法組成回文。目標是最少交換，不是任意構造一個回文。
面試官考察什麼
- 推導奇數頻次可行性條件。
- 從右側為左端字元選擇最近可用匹配。
- 證明貪心最優，並正確計算移動成本。
作答前的釐清問題
- 只能相鄰交換且每次成本為 1 嗎？
- 字元集是否任意，Unicode 碼點是否視為字元？
- 函式可以修改陣列，還是只回傳計數？
- 輸入規模是否允許 O(n²)？
30 秒回答框架
先統計奇數頻次；超過 1 次就無法組成回文。使用兩端指標，端點相等時向內收縮；不等時從右邊界向左尋找左端字元，把它透過相鄰交換冒泡到右端並累計移動次數。找不到匹配時，該字元必須是唯一中心，將它一步步移向中間。
分步深入
1. 證明可行性
回文的對稱位置成對出現，最多只有奇數長度的中心可以單獨存在，因此奇數頻次最多 1 個。先檢查可避免在不可行輸入上執行貪心。
2. 匹配邊界
對指標 i、j，若 s[i] 等於 s[j]，兩端都已固定。否則從 j 向 i + 1 搜尋 s[k] == s[i]。把該字元移到右端需要 j - k 次交換，且不會破壞已固定前綴。
3. 處理中心字元
找不到匹配時，s[i] 就是應放在中心的奇數頻次字元。每次向右交換一步，直到到達中間並計數。不能丟棄它，也不能假設第一輪就能直接找到中心。
4. 實作模擬
text
統計奇數頻次
若 odd_count > 1：回傳不可行
left = 0，right = n - 1，swaps = 0
當 left < right：
若 s[left] == s[right]：left 加一，right 減一，繼續
k = right
當 k > left 且 s[k] != s[left]：k 減一
若 k == left：交換 s[k] 與 s[k + 1]，swaps 加一
否則：將 s[k] 冒泡到 right，累計每次相鄰交換
left 加一，right 減一
回傳 swaps5. 分析複雜度與證明思路
每輪搜尋和冒泡最多 O(n)，共 O(n) 輪，因此時間 O(n²)，可變陣列外額外空間 O(1)。最近的匹配字元移動成本最低；更遠匹配至少需要同樣多的相鄰交換。中心情況由奇數頻次唯一性決定。
高品質示範回答
「先統計奇數頻次，超過 1 個就回傳不可行。然後比較兩端；不匹配時尋找靠近右邊界的相同字元並冒泡到位，加入移動距離；若找不到，它就是唯一奇數中心，就向中間移動。端點匹配後收縮視窗。模擬為 O(n²) 時間、O(1) 額外空間，最近匹配最優，因為更遠字元需要至少同樣多的相鄰交換。」
常見誤區
- 要求所有頻次都為偶數 → 奇數長度允許一個奇數頻次 → 最多允許一個。
- 隨便選匹配字元 → 移動可能不是最少 → 選靠近邊界的匹配。
- 丟掉找不到匹配的字元 → 少算中心移動 → 把它冒泡到中間。
- 雙指標直接交換不移動中間元素 → 丟失相鄰交換成本 → 模擬每次相鄰移動或使用等價資料結構。
追問與回答
能同時回傳最終回文嗎？
可以。保留可變陣列並回傳最終內容與計數；如需交換序列，可記錄每次相鄰交換。
大輸入如何最佳化？
用 Fenwick 樹或順序統計結構維護原始位置，讓移動成本在對數時間更新。貪心配對不變，只避免逐元素移動。
如果允許任意位置交換呢？
成本模型不同，最近匹配的距離證明不再適用。先明確操作規則，再設計新演算法。