Leetcode 424.替换后的最长重复字符

替换后的最长重复字符

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

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

示例 1:

输入:

s = "ABAB", k = 2

输出:

解释:

用两个'A'替换为两个'B',反之亦然。

示例 2:

输入:

s = "AABABBA", k = 1

输出:

解释:

将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。

子串 "BBBB" 有最长重复字母, 答案为 4。

思路：

题目的意思比较清楚，不过可能的情况有很多，不可能用代码去寻找最佳的替换位置，所以这里采用一种滑动窗口的方法。

定义start和end两个标记，中间的内容即是窗口，计算窗口内所有字母出现的次数，因为全是大写字母，所以可以用一个26位的数组来记录窗口内每个字母出现的次数。

找到窗口内出现最多的次数，加上允许替换的字母数k，看是否超过窗口宽度，如果超过了，说明窗口还可以更长，也就是说窗口内重复的字母的长度可以更长，就将end右移一位，形成新的窗口，然后继续重复上面的步骤。如果没超过，说明能构成的最长的重复字母长度已经到顶了，这时应该将start右移一位，来寻找新的可能的更长重复字母长度。

每次计算重复字母长度时，当出现更长的可能时，都更新最终的结果。

为了减少时间复杂度，我们不去每次都遍历窗口来计算出现的字母次数，而是在移动end或者start时，将对应位置的字母的次数加一或者减一。

要注意各种边界条件是什么。

 1 public class Solution {
 2     public int characterReplacement(String s, int k) {
 3         if (s.length() < 1) return 0;
 4         int start = 0;
 5         int end = 0;
 6         int res = 0;
 7         int[] charNum = new int[26];
 8         charNum[s.charAt(0) - 'A']++;
 9         while (s.length() > end) {
10             int maxChar = 0;
11             for (int i = 0; i < 26; i++) {
12                 if (charNum[i] > maxChar)
13                     maxChar = charNum[i];
14             }
15             if (maxChar + k > end - start) {
16                 end++;
17                 if (end < s.length())
18                     charNum[s.charAt(end) - 'A']++;
19             } else {
20                 charNum[s.charAt(start) - 'A']--;
21                 start++;
22             }
23             if (maxChar + k > res)
24                 res = maxChar + k <= s.length() ? maxChar + k : s.length();
25         }
26         return res;
27     }
28 }