MediumRating 1680

424. Longest Repeating Character Replacement

hash-tablestringsliding-window

解題說明

Longest Repeating Character Replacement

題目描述：給定字串 s 和整數 k，最多可以替換 k 個字元，使子字串中所有字元相同，求這樣的最長子字串長度。

解題思路：滑動視窗：維護視窗 [left, right] 中出現次數最多的字元數 maxFreq。視窗大小 - maxFreq = 需要替換的字元數；若 > k，移動左指標縮小視窗。關鍵：maxFreq 只增不減（不需要在縮小視窗時更新），這確保了視窗大小單調非減，最終答案即為最大視窗大小。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個字元最多進出視窗各一次。

空間複雜度：O(1) — 固定大小的計數陣列（26 個英文字母）。

虛擬碼

1. count[26] = 0, left = 0, maxFreq = 0
2. For right from 0 to n-1:
   a. Increment count[s[right]]
   b. maxFreq = max(maxFreq, count[s[right]])
   c. While (window_size - maxFreq) > k: shrink from left
   d. Update result = max(result, window_size)
3. Return result

其他解法

暴力滑窗 O(n²)：對每個左端點，擴展右端點並重計字符頻率 — 時間複雜度更差。

無滑窗單次掃描：一次掃描計算最大頻率，但無法找出對應區間 — 不完整。

延伸思考

若允許多種替換操作（而非單一字符）？
若 k 可變，如何查詢特定 k 的答案？
若要回傳替換的具體位置？

Longest Repeating Character Replacement — CaffeCode