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

题目链接：424. 替换后的最长重复字符

题目描述

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

核心思考：最大频数主导的滑动窗口

这道题是经典的滑动窗口变形问题。

关联题目： 本题在逻辑内核上与 1004. 最大连续1的个数 III 几乎如出一辙。只不过 1004 题仅限于 0 和 1 的二元状态，而这道题扩充到了 26 个大写字母的多元状态。

在这道题中，如何在滑动窗口内去判断“替换次数是否超标”依然是核心。我们可以逆向思考：无论窗口内有多少种字母，我们最终要构造的“全重复字符子串”，其底色必然是当前窗口内出现频率最高的那个字母。
因此，我们可以得出推论：
需要被替换的字符数量 = 当前窗口总长度 - 窗口内出现频率最高的字符数量。

当这个“需要替换的数量”超出了题目允许的自由额度 k 时，说明当前区间宣告失效，必须开始移动左边界收缩窗口。

细节：为什么左指针收缩时不需要同步降低记录的最大频率？

在代码逻辑中，我们维护了一个哈希频次数组 wordcount 和一个记录历史窗口最高频次的标量 cur_max_word_count。

当左指针 left 向右移动，弹出左侧字符时，我们理所当然地从 wordcount 中扣除了该字符的一次频数。但注意，这里我们通常不去同步减小 cur_max_word_count。

为什么可以这样做？因为我们的求解目标是寻求最长的合法窗口大小。
曾经达到的 cur_max_word_count 决定了当前窗口扩张的物理极限。即使某个高频字母离开窗口导致实际最高频降低，但在寻找到一个比过去历史记录更长、且内部拥有更大频数的字符集之前，这个较小的局部最高频状态对于打破极值没有任何贡献，因而不会错误放大最终结果 ans。这种延迟或惰性更新极为精巧地将时间复杂度降到最低。

解题思路 (Python)

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # 找当前窗口中出现频率最高的字母，然后算上替换的进行维护。
        l = len(s)
        left = right = 0
        ans = 0
        wordcount = [0] * 26
        cur_max_word_count = 0
        while right < l:
            # 当前字符的基数index是
            char = ord(s[right])-ord('A')
            wordcount[char] += 1
            cur_max_word_count = max(cur_max_word_count,wordcount[char])
            right += 1
            while right - left - cur_max_word_count > k:
                wordcount[ord(s[left])-ord('A')] -= 1
                left += 1
            ans = max(ans,right-left)
        return ans

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是字符串 s 的总长度。虽然内含了嵌套的 while 循环，但是双指针均只发生单调的不回退位移，即字符串每个字符最多只会触发一进一出两次操作边界扫描，保持完全线性运算。
• 空间复杂度：$O(|\Sigma|)$，其中 $|\Sigma|$ 代表字符集空间跨度。本题固定由 26 个纯大写英文字母矩阵组建测试用例，我们开辟维护频率状态的数组常驻体积为 26 个整型空间大小，严格折合属于 $O(1)$ 常熟级时间上限。