題目描述:給定字串 s 和整數 k,最多可以替換 k 個字元,使子字串中所有字元相同,求這樣的最長子字串長度。
解題思路:滑動視窗:維護視窗 [left, right] 中出現次數最多的字元數 maxFreq。視窗大小 - maxFreq = 需要替換的字元數;若 > k,移動左指標縮小視窗。關鍵:maxFreq 只增不減(不需要在縮小視窗時更新),這確保了視窗大小單調非減,最終答案即為最大視窗大小。
時間複雜度: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²):對每個左端點,擴展右端點並重計字符頻率 — 時間複雜度更差。
無滑窗單次掃描:一次掃描計算最大頻率,但無法找出對應區間 — 不完整。