Description
給定一個只包含大寫英文字母的字串
s和一個整數k，你最多可以將字串中的k個字元替換成任意其他大寫字母。回傳替換後能得到的最長連續相同字元子字串長度。
Example:
Input: s = “AABABBA”, k = 1 Output: 4
Intuition#
視窗內「需要替換的字元數 = 視窗長度 - 最高頻字元次數」，只要這個值不超過 k，視窗就合法。
- 維護一個滑動視窗，追蹤視窗內每個字元的頻率
- 如果
windowLen - maxFreq > k，代表需要替換的字元太多，收縮左邊界 - 關鍵洞察：
maxFreq不需要在收縮時精確遞減，因為只有更大的maxFreq才能產生更長的答案
Approaches#
1: Brute Force#
- 概念: 對每個起點嘗試擴展視窗，計算需要替換的字元數
- 時間複雜度:
O(n²) - 空間複雜度:
O(1)
Brute Force 程式碼
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#
- 概念: 維護視窗並追蹤最高頻字元次數，當替換數超過 k 時收縮左邊界
- 時間複雜度:
O(n) - 空間複雜度:
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
}
}🔑 Takeaways#
- Pattern: 可變長度滑動視窗 + 頻率計數
- 關鍵技巧: 「需要替換的字元數 = 視窗長度 - 最高頻字元次數」這個公式是核心，可應用於類似的「允許 k 次修改」問題