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

思路：滑动窗口

核心观察： 对于窗口 [left, right]，若要让窗口内所有字符变成同一个，最少需要替换的次数为：

窗口长度 - 窗口内出现次数最多的字符的频率

只要这个值 <= k，窗口就合法。于是问题转化为：用滑动窗口维护一个"最多替换 k 次即可全部相同"的最长区间。

关键技巧（窗口只增不减）： 当窗口不合法时，只把 left 右移一位、窗口长度保持不变，而不是收缩到合法。因为我们要的是最大长度，所以窗口长度单调不减，最终窗口大小就是曾经出现过的最大合法窗口长度。

classSolution{publicintcharacterReplacement(Strings,intk){int[]count=newint[26];// 窗口内各字符频率intleft=0;intmaxCount=0;// 历史窗口内出现过的最大频率intans=0;for(intright=0;right<s.length();right++){intidx=s.charAt(right)-'A';count[idx]++;maxCount=Math.max(maxCount,count[idx]);// 窗口长度 - maxCount > k 说明不合法if(right-left+1-maxCount>k){count[s.charAt(left)-'A']--;left++;// 窗口整体右滑，长度不变}ans=Math.max(ans,right-left+1);}returnans;}}

复杂度分析

· 时间复杂度：O(n)，right 指针遍历一次，left 最多也走 n 步。
· 空间复杂度：O(1)，固定 26 大小的计数数组。

关键点

1. 为什么用 if 而不是 while？
   用 while 收缩到合法，得到的仍是正确答案，但每次可能收缩多位。用 if 时窗口长度单调不减——不合法时 left 只走一步保持长度，合法时窗口扩张。由于 ans 只在窗口长度增长时更新，它最终等于历史最大合法窗口长度，结果依然正确。
2. 为什么 maxCount 收缩时不用减少？
   maxCount 代表历史最大频率。若窗口不合法是因为真实 maxCount 变小了，我们并不需要立刻修正——因为此时窗口长度没有超过历史答案，不会影响最终结果；而当窗口长度继续增长时，只有出现更大的真实 maxCount 才会被更新。这是该优化成立的依据。
3. count 数组需要清理吗？
   不需要。left 右移时同步 --count[…]，保证数组始终与当前窗口内容一致。

直观对比

写法 时间 特点
while 收缩到合法 O(n) 窗口语义清晰，便于讲解
if 只滑一步（本解法） O(n) 常数更小，窗口长度单调不减