leetcode算法题基础（十）滑动窗口（二）424 题 替换后的最长重复字符

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

注意:
字符串长度 和 k 不会超过 104。

示例 1:

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

输出:
4

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

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

输出:
4

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解释一下为什么我叫它“贪心的滑窗”，因为除了会“滑动”， 它还会“扩充”，这也是紧扣本题解法的核心要素。

滑动：窗口的左端和右端同时向右移动一位
扩充：窗口的左端固定，右端向右移动一位
审题：
题目给了我们一个字符串和k次替换字符的机会，对该字符串进行不多于k次替换操作后，求解只包含重复字符的最长子串长度。

思路：
用一个由左右索引构成的动态窗口去限定字符串的一个子串，并记录当前子串中最高频字符的数量。

窗口的左右索引分布为left、 right, 窗口长度为win_len=(left-right+1)
当前窗口中出现最多的字符数量 max_freq
1. 动态窗口如何初始化？
答：类似动态规划的思路，我们先初始化一个长度为0的窗口，从字符串的最左侧开始遍历

2. 什么时候扩充？
答：当子串符合要求时，向右扩充一位（贪心，子串已经满足要求了还要继续膨胀）
追问：子串符合要求(只包含重复字符)的情形
追答： win_len - max_freq <= k
解释：可替换次数k 足以将当前窗内所有字符都替换成最高频字符

3. 什么时候滑动？
答：当子串不符合要求时，整体向右滑动一位（搜索）
即 win_len - max_freq > k
注意窗口长度是不会减少的，即便后面搜索不到更优子串，也不会影响滑动之前的最优解

代码如下~

from collections import defaultd

作者：pover
链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement/solution/tan-xin-de-hua-dong-chuang-kou-si-lu-qing-xi-dai-m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

from collections import defaultdict


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        char_counter = defaultdict(int)  # 当前窗口内各字符数量，因为窗口是动态的，所以用哈希表可以更好维护
        
        left = right = 0  # 初始化动态窗的左、右指针
        max_freq = 0  # 当前窗口内出现最多字符的频数

        while right < len(s):  # 终止条件：右指针移动到最右
            char_counter[s[right]] += 1
            max_freq = max(max_freq, char_counter[s[right]])

            if (right - left + 1) - max_freq > k:  # 可替换次数k不足以将当前窗内所有字符都替换成最高频字符，滑动
                char_counter[s[left]] -= 1  # 左指针右移前，先删除窗口最左字符在窗口内的计数
                left += 1
            # else: 扩充，但扩充不需要更多额外的操作
            right += 1
        else:
            return right - left