leetcode424替换后的最长重复字符

leetcode424替换后的最长重复字符

二月 20, 2020

leetcode424替换后的最长重复字符

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意:
字符串长度 和 k 不会超过 104。

示例 1:
输入:
s = “ABAB”, k = 2
输出:
解释:
用两个’A’替换为两个’B’,反之亦然。

示例 2:
输入:
s = “AABABBA”, k = 1
输出:
解释:
将中间的一个’A’替换为’B’,字符串变为 “AABBBBA”。
子串 “BBBB” 有最长重复字母, 答案为 4。

滑动窗口，自己是真没想出来，看到评论才知道的。

滑动窗口解决的问题就是左窗口i和右窗口j怎么移动的问题.

左边怎么动：j-i+1>k+maxChara,maxChara是窗口内部此时字母最多的元素的个数，比如AAAAAB，maxChara就是A的个数5，CCCCCAAB，maxChara是C的个数5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int characterReplacement(String s, int k) {
        int[] index=new int[26];
        int max=0,result=0,maxChara=0;
        for(int i=0,j=0;j<s.length();j++) {
        	index[s.charAt(j)-65]++;
        	maxChara=Math.max(maxChara, index[s.charAt(j)]);
        	if(j-i+1-maxChara>k) {
        		i++;//左窗口右移
        		index[s.charAt(i)]--;//因为窗口右移了所以对应的计数器减一
        	}
        	result=Math.max(result, j-i+1);
        }
        return result;
    }

leetcode 2/100