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

题目

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

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

示例 1：

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

示例 2：

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

思路

首先，遇到这种类似于“求最长子字符串”的问题，就隐隐约约的感觉到滑动窗口（双指针）的影子了。

确实是使用双指针。两个指针均从字符串左端出发，每个迭代右指针右移一位，如果依然满足right - left + 1 <= k + maxCount，maxCount是字符的最大重复次数，则说明k还够用，左指针不动；如果不满足上式，说明k不够用了，左指针右移一位，从而维护好满足条件的最大区间长度。双指针移动的过程中区间长度绝不会变短。右指针是主动轮，左指针是从动轮（和二维迭代的本质区别，后者两个指针都是主动轮，从前往后遍历）。

在两个指针移动的过程中，维护好一个26个字母的数组，记录每个字母在当前区间中的出现次数，其中的最大值即为maxCount。

因为双指针都是从前往后遍历一次，因此时间复杂度为O(n)，n是字符串长度。

代码

复习双指针的写法（while判断条件）～

class Solution {
    public int characterReplacement(String s, int k) {
        int[] table = new int[26]; // 记录26个字母在滑动窗口中重复出现的次数
        int left = 0; // 滑动窗口左指针（从动轮）
        int right = 0; // 滑动窗口右指针（主动轮），滑动窗口是闭区间
        int maxCount = 0; // 重复出现次数最大的字母的重复出现次数
        while (right < s.length()) {
            table[s.charAt(right) - 'A']++; // 右指针的字母出现次数自增一次
            maxCount = Math.max(maxCount, table[s.charAt(right) - 'A']); // 最大重复次数只有可能是右指针上的新字母来挑战
            if (right - left + 1 > k + maxCount) { // k不够用了
                table[s.charAt(left) - 'A']--; // 左指针的字母出现次数自减一次
                left++; // 左指针右移
            }
            right++; // 右指针右移
        }
        return right - left; // 闭区间长度没有+1，因为跳出while循环之前right多增了一次
    }
}