1、题目描述
https://leetcode-cn.com/problems/longest-repeating-character-replacement/
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。
在执行上述操作后，找到包含重复字母的最长子串的长度。
注意：字符串长度 和 k 不会超过 10^4。
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。输入：s = "AABCABBB", k = 2
输出：6
解释：
将中间的一个'CA'替换为'BB',字符串变为 "AABBBBBB"。
子串 "BBBBBB" 有最长重复字母, 答案为 6。
2、代码详解
双指针（滑动窗口）
- 右边界先移动找到一个满足题意的可以替换 k 个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下；
- 然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串；
- 替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。
开区间写法：[left, right), 结果是right - left
class Solution(object):
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
n = len(s)
if n < 2:
return n
freq = [0] * 26 # 组维护每一个字符的出现次数,记录当前窗口字母出现的个数
max_count = 0 # 记录字符出现次数最多那个字符 的次数
res = 0
left = 0
right = 0
# [left, right) 内最多替换 k 个字符可以得到只有一种字符的子串
# 注意是开区间写法:right - left!!
while right < n:
freq[ord(s[right]) - ord('A')] += 1
# print('滑动右边界:', freq)
# 维护 maxCount，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加
max_count = max(max_count, freq[ord(s[right]) - ord('A')]) # 比较之前记录的最大数 和 当前字符的数量
right += 1 # !!
if right - left - max_count > k: # 若当前窗口大小 减去 窗口中最多相同字符的个数 大于 k 时,该区间内非最长重复字符超过了 k 个
# 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动
# 移出滑动窗口的时候，频数数组须要相应地做减法
freq[ord(s[left]) - ord('A')] -= 1 # 将窗口最左边的字符 在计数数组中减1
# print('滑动左边界:', freq)
left += 1
res = max(res, right - left)
return res闭区间写法[left, right], 结果是right - left + 1
class Solution(object):
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
n = len(s)
if n < 2:
return n
freq = [0] * 26 # 组维护每一个字符的出现次数,记录当前窗口字母出现的个数
max_count = 0 # 记录字符出现次数最多那个字符 的次数
res = 0
left = 0
right = 0
# [left, right]最多替换 k 个字符可以得到只有一种字符的子串
# 注意是闭区间写法：right - left + 1 ！！
while right < n:
freq[ord(s[right]) - ord('A')] += 1
# print('滑动右边界:', freq)
# 维护 maxCount，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加
max_count = max(max_count, freq[ord(s[right]) - ord('A')]) # 比较之前记录的最大数 和 当前字符的数量
if right - left + 1 - max_count > k: # 若当前窗口大小 减去 窗口中最多相同字符的个数 大于 k 时,该区间内非最长重复字符超过了 k 个
# 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动
# 移出滑动窗口的时候，频数数组须要相应地做减法
freq[ord(s[left]) - ord('A')] -= 1 # 将窗口最左边的字符 在计数数组中减1
# print('滑动左边界:', freq)
left += 1
res = max(res, right - left + 1)
right += 1 # ！！
return res- 时间：O(N)， N 是输入字符串 S 的长度
- 空间：O(A)， A 是输入字符串 S 出现的字符 ASCII 值的范围