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

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

示例

示例 1:

输入:
s = "ABAB", k = 2

输出:
4

解释:
用两个'A'替换为两个'B',反之亦然。
示例 2:

输入:
s = "AABABBA", k = 1

输出:
4

解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

解题思路

主要是用滑动窗口来解题。

1. 初始化窗口大小为0 -> begin = end = 0，并用一个字典memo来对窗口内的元素进行统计
2. 将end元素加入窗口，memo[s[end]] ++
3. 判定窗口是否能扩增
   1. if windows length < max_repeated_letter_count + K then ok
   2. else begin++ and memo[s[begin]] --
4. 重复2、3步骤，直到到达字符串的尾部

其中max_repeated_letter_count为窗口中出现的最大的重复字母数

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        from collections import defaultdict
        memo = defaultdict(int)
        begin = history_max = max_length = 0
        N = len(s)
        for end in range(N):
            memo[s[end]] += 1
            history_max = max(history_max, memo[s[end]])
            if end-begin+1 > k + history_max:
                memo[s[begin]] -= 1
                begin+=1
            max_length = max(max_length, end - begin + 1)
        return max_length

以及简化版，效率更高

    def characterReplacement(self, s: str, k: int) -> int:

        res = 0
        dic = {}
        max_len = 0

        for i in range(len(s)):
            dic[s[i]] = dic.get(s[i], 0) + 1
            max_len = max(max_len, dic[s[i]])

            if res - max_len < k:
                res += 1
            else:
                dic[s[i-res]] -= 1
        return res