424. Longest Repeating Character Replacement

Ref: https://leetcode-cn.com/problems/longest-repeating-character-replacement/

这道题是经典的双指针滑动窗口问题，其核心思路如下：

• 右边界先移动找到一个满足题意的可以替换 k 个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下；
• 然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串；
• 替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。

代码如下：

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        s = [x for x in s]
        l = len(s)
        if l <= 1:
            return l
        left = 0
        right = 0
        freq = [0 for _ in range(26)]
        max_count = 0
        result = 0
        while right < l:
            freq[ord(s[right]) - ord('A')] += 1
            max_count = max(max_count, freq[ord(s[right]) - ord('A')])
            right += 1
            if right - left > max_count + k:
                freq[ord(s[left]) - ord('A')] -= 1
                left += 1
            result = max(result, right - left)
        return result