424. 替换后的最长重复字符

Difficulty
Medium
Tags
滑动窗口
URL
https://leetcode-cn.com/problems/longest-repeating-character-replacement/
Star
 
给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回包含相同字母的最长子字符串的长度。
示例 1：
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。
示例 2：
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
提示：
  • 1 <= s.length <= 105
  • s 仅由大写英文字母组成
  • 0 <= k <= s.length

法1 滑动窗口

思路
这里有个优化，不需要每次都去重新更新max_count。
比如说"AAABCDEDFG" k=2，这个case，一开始A出现3次,max_count=3，但是当指针移到D时发现不行了，要移动left指针了。此时count['A']-=1，但是不需要把max_count更新为2。为什么呢？ 因为根据我们的算法，当max_count和k一定时，区间最大长度也就定了。当我们找到一个max_count之后，我们就能说我们找到了一个长度为d=max_count+k的合法区间，所以最终答案一定不小于d。所以，当发现继续向右扩展right不合法的时候，我们不需要不断地右移left，只需要保持区间长度为d向右滑动即可。如果有某个合法区间大于d，一定在某个时刻存在count[t]+1>max_count，这时再去更新max_count即可。
就是说后面的max_count只能比当前的大才能更新res，不然不可能是结果，所以max_count只需要往大更新即可
题解
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        wds = collections.defaultdict(int)
        if len(s) <= k:
            return len(s)
        max_num = 0
        l, r = 0, 0
        res = 0
        while r < len(s):
            cur_char = s[r]
            r += 1
            wds[cur_char] += 1

            max_num = max(max_num, wds[cur_char])
            # 使用 k 次机会都没法补救的
            while r - l - max_num > k:
                delet_char = s[l]
                l += 1
                wds[delet_char] -= 1
            
            res = max(res, r - l)

        return res