替换后的最长重复字符怎么用滑动窗口？maxCount 为什么不用回退？

简化版

维护一个窗口和窗口内出现次数最多的字符数 maxCount。若窗口长度 len - maxCount <= k，说明最多替换 k 个字符就能把窗口变成同一个字符；否则收缩左边界。maxCount 可以只增不减，因为它只用于判断窗口是否“可能保持有效长度”，不会让答案变小。

详细版

对任意窗口，要变成全相同字符，最优做法一定是保留窗口里出现次数最多的字符，把其他字符替换掉。所以需要替换的次数是 windowLength - maxFrequencyInWindow。如果这个值不超过 k，窗口有效，可以尝试更新答案；如果超过 k，就左边收缩。

例如 s="AABABBA", k=1，最长长度是 4，对应 "AABA" 或 "ABBA"，只需要替换一个字符。实现时用计数数组记录字符频次，右指针扩展时更新 maxCount，当 right-left+1-maxCount > k 时移动左指针。

面试常追问：左指针移动后 maxCount 可能已经不是真实最大频次，为什么不影响答案？因为保留偏大的 maxCount 最多让窗口晚一点收缩，但答案只记录历史可达到的最大长度；严格回退也可以，只是多做了不必要工作。

完整版教学

一、窗口有效性的公式

如果一个窗口长度是 len，其中出现最多的字符有 maxCount 个，那么把整个窗口变成同一个字符，最少替换次数就是 len - maxCount。因为保留最多的那类字符最划算，其他字符全部改成它。

例如窗口 "AABA" 长度 4，A 出现 3 次，B 出现 1 次，所以替换 1 次就能变成 "AAAA"。窗口 "ABBC" 长度 4，最多字符 B 出现 2 次，至少要替换 2 次。

needReplace = windowLength - maxFrequency
valid       = needReplace <= k

记忆钩子：这题不是问“换成哪个字符”，而是问“窗口里最多的字符能不能撑起整个窗口”。

二、为什么可以滑动窗口

右指针扩张时，窗口长度增加，可能让答案变大；如果替换次数超过 k，说明当前窗口已经无法靠 k 次替换变成统一字符，需要移动左指针缩短窗口。这个过程满足单调推进：右指针只向右，左指针也只向右。

对于 s="AABABBA", k=1，窗口从 "A" 扩到 "AABA" 时有效，长度 4；继续扩到 "AABAB"，长度 5，最多字符 A 有 3 个，需要替换 2 个，超过 k，所以收缩。

right 扩张 -> 统计字符
如果 len - maxCount > k:
    left 收缩一格
窗口重新用于更新答案

三、maxCount 为什么可以只增不减

严格来说，左指针移走字符后，窗口里的真实最大频次可能下降。但这题可以保留历史 maxCount，原因是它只影响“是否需要收缩”的判断，不会让最终答案超过可行最大长度。

如果 maxCount 偏大，窗口可能暂时看起来有效，左边界收缩得晚一些。但这个偏大的值来自某个历史窗口，说明历史上确实出现过这么多相同字符；算法记录的是最大窗口长度，当窗口长度再增长到需要更新答案时，它对应的长度也必须被某个历史最大频次支撑过。

写法	是否正确	代价
`maxCount` 只增不减	正确	O(n)，实现简单
每次收缩后重算最大频次	正确	字母表固定时仍可 O(26n)，但啰嗦
完全不维护最大频次	不适合	无法判断替换次数

四、代码模板

如果题目限定大写英文字母，用长度 26 的数组即可。若字符集更大，可以换成哈希表。

int characterReplacement(String s, int k) {
    int[] cnt = new int[26];
    int left = 0, maxCount = 0, ans = 0;
    for (int right = 0; right < s.length(); right++) {
        int idx = s.charAt(right) - 'A';
        cnt[idx]++;
        maxCount = Math.max(maxCount, cnt[idx]);
        while (right - left + 1 - maxCount > k) {
            cnt[s.charAt(left) - 'A']--;
            left++;
        }
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
}

注意 while 写成 if 在这题也常能通过，因为每次右边只加一个字符，非法程度最多增加 1；但面试中写 while 更通用，适用于更多滑动窗口题。

五、手推样例

样例 s="AABABBA", k=1。当窗口是 [0..3] = "AABA" 时，长度 4，A 出现 3 次，需要替换 1 次，答案更新为 4。

右指针到 4，窗口 "AABAB" 长度 5，历史 maxCount=3，需要替换 2 次，超过 k，左指针右移，窗口变为 "ABAB"。继续扫描后最大长度仍是 4。

窗口    len  maxCount  len-maxCount  是否有效
A       1      1           0          是
AA      2      2           0          是
AAB     3      2           1          是
AABA    4      3           1          是
AABAB   5      3           2          否，收缩

六、常见误区与追问

误区：把窗口内所有非目标字符逐个枚举替换。 题目只要最长长度，不需要真的构造替换后的字符串。
误区：每次都枚举 26 个字符作为目标字符。 可以做，但维护 maxCount 更直接。
误区：认为 maxCount 不回退一定错误。 对这题记录最大长度的写法是安全的，严格重算只是更保守。
追问：如果字符集不是大写字母怎么办？ 把数组计数换成哈希表，逻辑不变。
追问：为什么窗口非法时要收缩左边？ 因为右边继续扩只会让长度更大，若没有更高频字符支撑，替换次数不会自动下降。
追问：这题和无重复字符最长子串有什么区别？ 那题约束是“每个字符最多一次”，这里约束是“非最多字符个数不超过 k”。

七、复杂度与边界

右指针遍历 n 次，左指针最多移动 n 次，所以时间 O(n)。计数数组固定 26 个元素，空间 O(1)；若使用哈希表，空间与字符集大小相关。

边界上，k=0 时题目退化为求最长连续相同字符；k >= n 时答案可以是 n。空串如果平台允许输入，应返回 0。

s = "ABAB", k = 2
任意保留 A: 替换两个 B -> "AAAA"
答案 = 4

八、加强记忆

这题的抓手是公式 窗口长度 - 最多字符次数 <= k。右边负责扩张答案空间，左边负责把非法窗口拉回约束内，maxCount 记录历史最高支撑力。面试时把“保留最多字符、替换其余字符”的推导讲清楚，比单纯背窗口模板更可靠。

简化版

详细版