【滑动窗口】替换后的最长重复字符

题目

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

---

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回包含相同字母的最长子字符串的长度。

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 10^5
• s 仅由大写英文字母组成
• 0 <= k <= s.length

解题

方法一：滑动窗口

思路

滑动窗口模板题。
维护一个 maxCnt 用来标识滑动窗口中出现次数最多的字符出现的次数，maxCnt + k 小于窗口的大小时（即在窗口内替换 k 个字符不够时）收缩窗口。

代码

class Solution {
    static final int HASH_LEN = 'Z' + 1;

    public int characterReplacement(String s, int k) {
        int[] window = new int[HASH_LEN];
        char[] chs = s.toCharArray();
        int n = chs.length;
        int left = 0, right = 0;
        int maxCnt = 0, maxLen = 0;
        while (right < n) {
            maxCnt = Math.max(maxCnt, ++window[chs[right++]]);
            while (right - left > maxCnt + k) {
                maxCnt = Math.max(maxCnt, --window[chs[left++]]);
            }
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }
}