#424
Medium
滑动窗口
Longest Repeating Character Replacement
求最多替换 k 次后可变成同一字符的最长子串。
StringSliding Window
题目定位
窗口合法条件是 windowLength - maxFrequency <= k，因此它是一个非常标准的“围绕主频统计维护合法性”的滑动窗口。
关键观察
需要替换的字符数，等于窗口长度减去窗口内最高频字符的出现次数。
目标复杂度
O(n) / O(1)
这题的解法思路怎么拆
1
窗口合法条件是 windowLength - maxFrequency <= k，因此它是一个非常标准的“围绕主频统计维护合法性”的滑动窗口。
2
需要替换的字符数，等于窗口长度减去窗口内最高频字符的出现次数。
3
先确认答案确实可以由一个移动的连续区间推导出来。
4
选好窗口状态：和、不同元素个数、频次、匹配字符数等。
参考实现
Python# Generic pattern template
# Variable size sliding window
left = 0
window = {}
answer = 0
for right, value in enumerate(nums):
add(window, value)
while not is_valid(window):
remove(window, nums[left])
left += 1
answer = update(answer, left, right, window)
# Fixed size sliding window
window = initialize(nums[:k])
answer = evaluate(window)
for right in range(k, len(nums)):
remove(window, nums[right - k])
add(window, nums[right])
answer = update(answer, right - k + 1, right, window)
常见坑点
warning
在每次收缩时都试图精确重算 max frequency，增加复杂度。
warning
把主频字符数量和不同字符个数混为一谈。
高频追问
为什么 max frequency 偶尔陈旧，答案仍然正确？
它和无重复字符最长子串的窗口条件有什么本质区别？
继续刷相关题
先把 滑动窗口 这个模式刷成体系，再去做更难变体。