MediumRating 1878

1234. Replace the Substring for Balanced String

stringsliding-windowtwo-pointers

解題說明

Replace the Substring for Balanced String

題目描述：給定只含 'Q'、'W'、'E'、'R' 四種字符的字串 s，長度為 n（n 能被 4 整除）。選擇一個子字串進行替換（替換成任意字符組合），使替換後整個字串每種字符恰好出現 n/4 次。求最短替換子字串的長度。

解題思路（滑動視窗）：

關鍵觀察：若窗口外（即保留不動的部分）每種字符的計數都 ≤ n/4，則窗口內的字符可以被任意調整以補齊剩餘配額，整個字串即可達到平衡。

因此問題轉化為：找最短視窗使得窗口外每種字符計數均 ≤ n/4。

演算法：

先統計全字串各字符頻率 freq，設 target = n / 4。
若已平衡（所有字符計數 = target），回傳 0。
雙指針 l = 0, r = 0，維護窗口外頻率（初始等於全局頻率）：
- 每次將 s[r] 加入窗口（窗口外計數 -1），右移 r。
- 若窗口外所有字符計數均 ≤ target（條件滿足），嘗試縮小視窗：將 s[l] 移出窗口（計數 +1），右移 l，更新最小長度。
- 繼續直到條件不滿足為止。
重複直到 r 到達末尾，回傳最小窗口長度。

C++ 解法

複雜度分析

時間複雜度：O(n · |Σ|) — 雙指針各最多移動 n 次，每次 isBalanced 檢查 O(|Σ|) = O(4) = O(1)，整體為 O(n)。

空間複雜度：O(|Σ|) = O(1) — 字符集大小固定為 4，頻率表為常數大小。

虛擬碼

1. Count freq of each char in s. target = n / 4.
2. If all freq == target: return 0.
3. l = 0, ans = n.
4. For r in 0..n-1:
   a. freq[s[r]]--  (s[r] enters window).
   b. While all freq[c] <= target (outside is balanced):
      - ans = min(ans, r - l + 1).
      - freq[s[l]]++  (s[l] leaves window).
      - l++.
5. Return ans.

其他解法

方法二：二分搜尋視窗長度

二分答案（最短視窗長度 len），對每個 len 用線性掃描判斷是否存在長度為 len 的視窗使外部平衡。固定長度視窗可用前綴和 O(1) 更新頻率，判斷 O(1)，每次二分 O(n)，總體 O(n log n)。比雙指針慢，但思路也清晰。

方法三：枚舉所有子字串

暴力枚舉所有子字串 s[l..r]，對每個子字串計算若替換後能否平衡（檢查外部頻率是否均 ≤ target）。時間 O(n³)（枚舉 O(n²) + 頻率計算 O(n)），遠超時間限制，僅作為正確性驗證。

方法四：前綴和優化枚舉

用前綴和陣列將每個子字串的頻率計算降至 O(1)，枚舉降至 O(n²)，結合剪枝可通過部分測資。但仍不如雙指針的 O(n) 最優解。

延伸思考

若字符集擴展為任意 k 種字符（字串長度保證為 k 的倍數），isBalanced 的時間複雜度為 O(k)，整體演算法的複雜度如何變化？
若允許替換多個不連續的子字串（而非一個連續片段），問題轉化為什麼？是否更簡單？
此題的「窗口外滿足條件 → 窗口內可任意補齊」思路是滑動視窗的一種變形（從「窗口內滿足條件」轉為「窗口外滿足條件」），還有哪些題型採用類似的「互補視窗」思路？