【LeetCode】424. 替换后的最长重复字符
424. 替换后的最长重复字符
知识点：字符串，滑动窗口；
题目描述
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意：字符串长度 和 k 不会超过 104。
示例
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
解法一：滑动窗口
这道题其实挺复杂的，里面有一些细节很难想；
想一下滑动窗口模板：
这道题目的条件时什么：当前窗口里出现次数最多的字母+k等于窗口长度
当达到这个条件后，如果下一个字符不是出现最多的字符，那左窗口就要移动了。
所以我们需要一个变量来记录当前窗口哪个字母出现的最大次数
class Solution {
public int characterReplacement(String s, int k) {
int[] num = new int[26];
int n = s.length();
int maxn = 0;
int left = 0, right = 0;
while (right < n) {
int indexR = s.charAt(right) - 'A';
num[indexR]++;
//求窗口中曾出现某字母的最大次数
//计算某字母出现在某窗口中的最大次数，窗口长度只能增大或者不变
//这样做的意义：我们求的是最长，如果找不到更长的维持长度不变返回结果不受影响
maxn = Math.max(maxn, num[indexR]);
//如果选择了maxn，那说明又多消耗了一个k；检查一下k还够不够用了，不够用的话整体移动，注意窗口大小是不变的。
//长度len=right-left+1,以下简称len
//len>字母出现最大次数+替换数目,说明k不够用了，这时候得把窗口向左移；
//分析一下，替换数目是不变的=k,字母出现最大次数是可能变化的，因此，只有字母出现最大次数增加的情况，len才能拿到最大值
//left和right一起移动,len不变的
if (right - left + 1 - maxn > k) {
//这里要减的，因为left越过该点，会对最大值有影响
num[s.charAt(left) - 'A']--;
left++;
}
//走完这里的时候，其实right会多走一步
right++;
}
//因为right多走一步，结果为(right-1)-left+1==right-left
return right - left;
}
}
细节：
- 1.num中存的是什么：num中放的是当前窗口中各字母的长度，所以当我们将左边界移动的时候，要把左边界那个移出去的元素次数-1；
- 2.maxn这个变量：要注意maxn这个变量是在维持一个历史窗口中的最大值。为什么维持一个历史最大值，而不是当前窗口，从根本原因就在于窗口是只增不减的；如果遍历到的right能够不消耗k，那就可以right++，继续窗口扩张；如果遍历到的right更多的消耗了k，那就要看消耗后k还够不够用了，要是不够用了，那把整个窗口进行滑动，这时的窗口大小不变；
比如一个子串k=2,然后有一段他的最大重复个数maxn是4，这时候他的长度是6，然后移动滑动窗口到另一段，如果这一串的最大重复个数小于4，那一定不会得到一个大于6的结果，所以记录历史最大值是可以了。记住我们找的是最长，如果找不到更长，那就维持不变就可以了
相关链接
版权声明：本文为Curryxin原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。