514，双指针解替换后的最长重复字符

Original 山大王wld 数据结构和算法 2022-05-19

收录于合集 #算法图文分析 161个

In one second your whole life can change. It only takes a moment for everything to feel quite different.

生命真是瞬息万变，只要片刻，一切就截然不同了。

问题描述

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

注意：字符串长度和 k 不会超过 10^4。

示例 1：

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

双指针解决

这是一道典型的滑动窗口问题。在一个窗口内假如出现次数最多的那个字符出现的次数是a，窗口的长度是b，只要满足a+k>=b，我们就可以把窗口中的其他字符全部替换为出现次数最多的那个字符。

比如在窗口中有字符串"ABAABAB"，如果k大于等于3，我们就可以把字符串中的所有字符B替换为A。

相反如果a+k<b，我们是没法把窗口内的其他字符全部替换为出现次数最多的那个字符。比如字符串"ABAABBA"，如果k小于3，我们是不能把字符串中的所有字符B全部替换为A的。

搞懂了上面的分析过程，我们再来看一下这题的解决思路。

首先使用两个指针left和right，分别指向窗口的左边和右边。刚开始的时候left和right都指向第一个字符，也就是窗口的大小是1。

接着移动right，也就是扩大窗口，然后再判断窗口内相同字母最多的数量加上K是否小于窗口的大小。如果小于，说明窗口内其他的字母不能替换为最多的那个字母，我们要移动left，也就是缩小窗口的大小。如果大于，说明窗口内其他的字母是可以替换为最多的那个字母的，然后窗口左边界不变，移动右边界，扩大窗口，继续上面的循环……，直到右边界超出字符串为止。

我们就以示例2为例画个图来看一下会更明白

搞懂了上面的过程，我们再来看下代码

 1public int characterReplacement(String s, int k) {
 2    //字符串的长度
 3    int length = s.length();
 4    //用来存放对应字母的个数，比如字母A的个数是map[0],
 5    //字母B的个数是map[1]……
 6    int[] map = new int[26];
 7    int left = 0;//窗口左边的位置
 8    //窗口内曾经出现过相同字母最多的数量
 9    int maxSameCount = 0;
10    int right = 0;//窗口右边的位置
11    //满足条件的最大窗口，也就是可以替换的最长子串的长度
12    int maxWindow = 0;
13    //窗口的左边先不动，移动右边的位置
14    for (; right < length; right++) {
15        //统计窗口内曾经出现过相同字母最多的数量
16        maxSameCount = Math.max(maxSameCount, ++map[s.charAt(right) - 'A']);
17        //如果相同字母最多的数量加上k还小于窗口的大小，说明其他的字母不能全部替换为
18        //最多的那个字母，我们要缩小窗口的大小，顺便减去窗口左边那个字母的数量，
19        //因为他被移除窗口了，所以数量要减去
20        if (k + maxSameCount < right - left + 1) {
21            map[s.charAt(left) - 'A']--;
22            left++;
23        } else {//满足条件，要记录下最大的窗口，
24            maxWindow = Math.max(maxWindow, right - left + 1);
25        }
26    }
27    return maxWindow;
28}