給定一個只包含大寫英文字母的字串
s和一個整數k，你最多可以將字串中的k個字元替換成任意其他大寫字母。回傳替換後能得到的最長連續相同字元子字串長度。
Example:
Input: s = “AABABBA”, k = 1 Output: 4
Intuition
TIP
視窗內「需要替換的字元數 = 視窗長度 - 最高頻字元次數」，只要這個值不超過 k，視窗就合法。
- 維護一個滑動視窗，追蹤視窗內每個字元的頻率
- 如果
windowLen - maxFreq > k，代表需要替換的字元太多，收縮左邊界 - 關鍵洞察：
maxFreq不需要在收縮時精確遞減，因為只有更大的maxFreq才能產生更長的答案
Approaches
1. Brute Force — O(n²) / O(1)
- Idea: 對每個起點嘗試擴展視窗，計算需要替換的字元數
- Time:
O(n²) - Space:
O(1)
Brute Force Code
class Solution {
fun characterReplacement(s: String, k: Int): Int {
var result = 0
for (i in s.indices) {
val count = IntArray(26)
var maxFreq = 0
for (j in i until s.length) {
count[s[j] - 'A']++
maxFreq = maxOf(maxFreq, count[s[j] - 'A'])
if (j - i + 1 - maxFreq <= k) {
result = maxOf(result, j - i + 1)
} else {
break
}
}
}
return result
}
}⭐ 2. Sliding Window — O(n) / O(1)
- Idea: 維護視窗並追蹤最高頻字元次數，當替換數超過 k 時收縮左邊界
- Time:
O(n) - Space:
O(1)（固定 26 個字母）
class Solution {
fun characterReplacement(s: String, k: Int): Int {
val count = IntArray(26)
var left = 0
var maxFreq = 0
var result = 0
for (right in s.indices) {
count[s[right] - 'A']++
maxFreq = maxOf(maxFreq, count[s[right] - 'A'])
if (right - left + 1 - maxFreq > k) {
count[s[left] - 'A']--
left++
}
result = maxOf(result, right - left + 1)
}
return result
}
}WARNING
maxFreq 在左邊界收縮時不需要更新（不減少），因為只有當出現更高頻率時才可能產生更長的合法視窗。這是一個常見的最佳化技巧。
🔑 Takeaways
- Pattern: 可變長度滑動視窗 + 頻率計數
- Key trick: 「需要替換的字元數 = 視窗長度 - 最高頻字元次數」這個公式是核心，可應用於類似的「允許 k 次修改」問題