- 标签:哈希表、字符串、滑动窗口
- 难度:中等
描述:给定一个仅由大写英文字母组成的字符串
要求:在进行上述操作后,找到包含重复字母的最长子串长度。
说明:
-
$1 \le s.length \le 10^5$ 。 -
$s$ 仅由大写英文字母组成。 -
$0 \le k \le s.length$ 。
示例:
- 示例 1:
输入:s = "ABAB", k = 2
输出:4
解释:用两个'A'替换为两个'B',反之亦然。
- 示例 2:
输入:s = "AABABBA", k = 1
输出:4
解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
可能存在其他的方法来得到同样的结果。
先来考虑暴力求法。枚举字符串 s 的所有子串,对于每一个子串:
- 统计子串中出现次数最多的字符,替换除它以外的字符 k 次。
- 维护最长子串的长度。
但是这种暴力求法中,枚举子串的时间复杂度为
- 使用 counts 数组来统计字母频数。使用 left、right 双指针分别指向滑动窗口的首尾位置,使用 max_count 来维护最长子串的长度。
- 不断右移 right 指针,增加滑动窗口的长度。
- 对于当前滑动窗口的子串,如果当前窗口的间距 > 当前出现最大次数的字符的次数 + k 时,意味着替换 k 次仍不能使当前窗口中的字符全变为相同字符,则此时应该将左边界右移,同时将原先左边界的字符频次减少。
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
max_count = 0
left, right = 0, 0
counts = [0 for _ in range(26)]
while right < len(s):
num_right = ord(s[right]) - ord('A')
counts[num_right] += 1
max_count = max(max_count, counts[num_right])
right += 1
if right - left > max_count + k:
num_left = ord(s[left]) - ord('A')
counts[num_left] -= 1
left += 1
return right - left
-
时间复杂度:$O(n)$,其中
$n$ 为字符串的长度。 -
空间复杂度:$O(|\sum|)$,其中
$\sum$ 是字符集,本题中$| \sum | = 26$ 。