替换后的最长重复字符
思路
双指针
通过双指针维护一个滑动窗口,通过对右指针-左指针算出窗口大小,判断条件为窗口大小减去重复字符出现的最大次数与可替换次数k进行比较,如果大于k次之后则需要进行左指针右移,重复以上步骤。
题目中特殊条件“仅为大写英文字母”,那么可以通过维护一个26位的数组来对出现次数进行维护,然后存放到变量中进行比较得出字符重复出现的最大次数。
class Solution{
public int charReplacement(String s, int k){
int[] chars = new int[26]; // 通过26位的数组维护滑动窗口中每个字符出现的次数
int left=0,right=0; //左右指针
int n=s.length();
int maxn = 0; // 重复字符出现的最大次数
while(right<n){
chars[s.charAt(right)-'A']++; //计数
maxn = Math.max(maxn, chars[s.charAt(right)-'A']);//遍历过程中维护重复字符出现的最大次数;
if(right-left+1-maxn>k){
chars[s.charAt(left)-'A']--;//左指针右移,需要将之前的左指针对应的字符计数减一
left++;
}
right++;
}
return right-left;
}
}