Longest Repeating Character Replacement
你会得到一个由大写英文字母组成的字符串 s 和一个整数 k。你最多可以选择 s 中的 k 个位置，并将每个位置上的字母改成任意其他大写字母。
返回最长子字符串的长度。子字符串是指相邻的一段字母。经过修改后，这段字母只包含同一个重复字母。
函数
- sstring
- 大写字母组成的字符串
- kinteger
- 你最多可以更改的字母数
- 返回值integer
- 你能构成的只包含同一个字母的最长子串的长度
约束条件
1 ≤ s.length ≤ 5 × 104s只包含大写英文字母。0 ≤ k ≤ s.length
示例
- 输入
- s = "BAAACAB"k = 1
- 输出
- 5
- 解释
- 把
C改成A后，索引 1 到 5 就会读作AAAAA。两个长度为 6 的窗口都包含一个B和C，所以都需要进行两次更改。
- 输入
- s = "AABBBAB"k = 2
- 输出
- 6
- 解释
- 索引 1 到 6 存放着
ABBBAB，把两个A都改掉后，就会得到BBBBBB。整个字符串的 7 个字符中只有 4 个B，所以需要进行 3 次修改。
- 输入
- s = "WXYZ"k = 0
- 输出
- 1
- 解释
- 由于不允许进行任何更改，答案就是字符串中已有的最长连续段。每个字母都与相邻字母不同，因此这段连续内容只有一个字母。
进阶
如果 s 可以存储任意字符，而不只是 26 个大写字母，会有什么变化？
提示
逐个打开提示，每个都会多透露一点。
对于一个固定的子字符串，其他每个字母应该变成哪个字母？这需要多少次更改？
当子字符串的长度减去其中出现次数最多的字母的次数后不超过
k时，该子字符串是可达的。沿着字符串向前移动窗口的两端，找出符合这一规则的最长窗口。保留 26 个计数和最高计数
top。在右侧添加一个字母；如果此时窗口需要更改的次数超过k，就从左侧移除一个字母，这样长度就保持不变。窗口不需要缩小，top也不需要减小。
题解
保留子字符串中出现次数最多的字母，并替换其余字母：长度为 len、出现次数最多的字母出现了 top 次的子字符串，需要替换 len - top 个字母。滑动窗口只需遍历一次，就能找到满足 len - top ≤ k 的最长子字符串，因为窗口不需要缩小，top 也不需要减小。
检查每个子字符串
结果正确，但无法在最大的测试中运行完毕
思路
对于每个起点，每次将终点向后扩展一个字母，更新每个字母的计数和 top，并检查 len - top ≤ k。每个新子字符串只需更新一次，无需重新计数；而且每个子字符串都会被检查，因此不会漏掉最长的可达子字符串。
长度为 n 的字符串大约有 n²/2 个子字符串：当 n = 5 × 10^4 时，需要检查 1.25 × 10^9 次。
算法
- 将
best设为 0。 - 对于每个起始索引，将 26 个计数和
top重置为 0。 - 将
end从起始位置移到最后一个索引。将s[end]计入对应的计数，如果该计数现在是最高的，就增大top。 - 如果
end - start + 1 - top ≤ k，且长度大于best，就保存该长度。 - 返回
best。
def characterReplacement(s, k):
n = len(s)
best = 0
for start in range(n):
count = [0] * 26 # letters in s[start..end]
top = 0 # count of the most common letter there
for end in range(start, n):
c = ord(s[end]) - ord('A')
count[c] += 1
top = max(top, count[c])
# Every letter that is not the most common one must change.
if end - start + 1 - top <= k:
best = max(best, end - start + 1)
return best每个目标字母使用一个滑动窗口
思路
先选择最终要变成的字母。如果最后整段都变成 A，你要找的是最多包含 k 个非 A 字母的最长子字符串。
让 right 在字符串上向右移动，并统计窗口中的非目标字母数量。当数量超过 k 时，向前移动 left，直到数量重新回到 k。窗口超出允许范围后，即使继续扩大也不会变得符合条件，因此 left 不会向回移动。对于每个 right，窗口都是以它结尾的最长有效窗口。
对全部 26 个字母分别运行，并保留最好的结果：最多对 5 × 10^4 个字母进行 26 次线性遍历。只有因为字母表很小，复杂度才能保持为 O(n)。
算法
- 对于从
A到Z的每个目标字母，都以left = 0和others = 0开始一个窗口。 - 让
right遍历字符串。如果s[right]不是目标字母，就将others加 1。 - 当
others > k时，将left向前移动；如果离开窗口的字母不是目标字母，就将计数减 1。 - 如果
right - left + 1大于best，就保存它。 - 遍历完全部 26 个字母后，返回
best。
def characterReplacement(s, k):
best = 0
for target in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
left = 0
others = 0 # letters in s[left..right] that are not target
for right in range(len(s)):
if s[right] != target:
others += 1
# Too many letters to change: drop letters from the left.
while others > k:
if s[left] != target:
others -= 1
left += 1
best = max(best, right - left + 1)
return best一个永不缩小的窗口
思路
为窗口维护 26 个计数值，以及 top，也就是最高计数。当加入 s[right] 后，窗口的代价变得太高时，就从左侧移除一个字母：窗口会滑动并保持长度不变，因为只有更长的窗口才能打破记录。否则，窗口长度就增加 1。它的长度始终是目前的最佳长度，因此答案是 n - left。
当一个字母离开窗口时，不要调整 top，即使它现在比实际计数更高。滑动后，窗口长度恰好是 top + k，因此要让窗口增长，必须有某个字母出现 top + 1 次，此时 top 也会随之增加。过时的 top 只会让窗口滑动，而滑动不会打破记录。
在 BAAACAB 中，当 k = 1 时，BAAAC 需要 2 次更改，因此窗口滑动为 AAAC。下一个 A 会让 top 增加到 4，窗口也会增长为 AAACA，长度为 5。
算法
- 保留 26 个计数，
left = 0和top = 0。 - 让
right在字符串上向右移动：将s[right]加入对应的计数，如果该计数现在更高，就增大top。 - 如果
right - left + 1 - top > k，就从计数中移除s[left]，并将left向右移动一步。不要减小top。 - 返回最终窗口长度
n - left。
def characterReplacement(s, k):
count = [0] * 26 # letters inside the window s[left..right]
left = 0
top = 0 # the highest count any letter has reached in a window
for right in range(len(s)):
c = ord(s[right]) - ord('A')
count[c] += 1
top = max(top, count[c])
# Needs more than k changes: slide the window instead of growing it.
if right - left + 1 - top > k:
count[ord(s[left]) - ord('A')] -= 1
left += 1
# The window only grew when a longer valid substring was found.
return len(s) - left
易错点和边界情况
- 把
k加到最长连续段的长度上。在AAAB中，k = 3时，结果是 6，比字符串本身还长。在BAAACAB中，k = 1时，结果是 4，但把C改掉后，两段就能合并成长度为 5 的一段。 - 统计与窗口首字母不同的字符，而不是与窗口中出现最多的字母不同的字符。
BAAA只需要改 1 个字符，不是 3 个。 - 在使用
while缩小窗口并重新计算实际最大值的循环中，返回n - left。窗口会变短，所以要单独保存一个best。 - 把窗口长度计算为
right - left。两端都在窗口内，所以要加 1。
常见问题3
最长重复字符替换的时间复杂度是多少？
单窗口解法的运行时间为 O(n)，其中 n 是 s 的长度：right 会遍历每个字母一次，而 left 每步最多移动一次。它使用 O(1) 的额外空间，包括 26 个计数值和几个整数。
这和“无重复字符的最长子字符串”有什么不同？
两者都会沿着字符串移动两个边界，但判断窗口是否有效的规则不同。前者要求窗口中不能有重复字符，因此窗口会不断缩小，直到重复字符消失。这里，窗口长度减去出现次数最多的字符的数量必须小于或等于 k，因此窗口可以保持固定长度滑动。
这个问题可以用二分查找解决吗？
是的。如果长度为 L 的子字符串可以达到，那么其中每个更短的子字符串也都可以达到，因此你可以对 L 进行二分查找。对于每个 L，滑动一个长度固定的窗口，并检查是否存在某个位置最多需要 k 次更改。这种方法的时间复杂度是 O(n log n)，比单窗口解法慢。
def characterReplacement(s, k):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "BAAACAB" k = 1
预期输出
5