424. 替换后的最长重复字符
Difficulty: 中等
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 _k _次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意：字符串长度 和 k 不会超过 104。
示例 1：
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。
示例 2：
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
Solution
思路：清晰的题解，利用滑动窗口进行解答。核心的想法就是，维护一个窗口，窗口的字符是可以通过替换变成一个重复字符子串，那么窗口的长度就是重复字符的个数加上K。
Language: java
class Solution {
public int characterReplacement(String s, int k) {
if(s.length() < k) return s.length();
char[] c = s.toCharArray();
int[] alp = new int[26]; //用来存放在窗口中的字符个数
int max = 0, left=0, right=0;
int hisMaxChar = 0; //记录在窗口中出现次数最多的那个字符
while(right<c.length){
int index = c[right] - 'A';
alp[index]++; //更新字符出现的次数
if(alp[hisMaxChar] < alp[index]){ //更新窗口中最多个数
hisMaxChar = index;
}
if(right-left+1 > alp[hisMaxChar]+k){
//当窗口的长度大于最大个数加K时，说明在窗口中，替换后的字符长度仍不是最长的
//此时，将窗口进行平移，移出窗口的字符在alp[]中减一
alp[c[left] - 'A'] --;
left++;
//Q：为啥窗口不缩小而是进行平移？A：我的理解是，要缩小也行，但需要再用一个变
//量记录窗口的最大值。观察可以发现，窗口其实可以不用缩小，因为窗口内不会产生
//不连续的重复子串，若窗口内有不连续的重复子串，那么它一定小于之前的长度。
}
right++;
}
return right - left;
}
}