替换后的最长重复字符

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

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

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

示例 2：
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
通过次数22,885提交次数44,806

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

滑动窗口+哈希表

利用滑动窗口维护最大值，利用哈希表统计在滑动窗口内的字母的种类和数量

左边界 $l$ 不动滑动窗口一直扩展右边界 $r$ 直至

• 如果滑动窗口中的出现次数最多元素的数量 $num_{mode}$,使得$num_{mode}+k<r-l$，需要左边界向右移动一个位置；
• 否则继续右移右边界 $r$
• 在窗口变化的过程中保证窗口的大小不缩小，最终窗口的大小就是结果

class Solution {
    public int characterReplacement(String s, int k) {
        int l = 0, r = 0;           // 滑动窗口的左右边界
        int[] hash = new int[26];   // 统计在滑动窗口内的字母的种类和数量

        int max = 0;
        int n = s.length();

        while (r < n) {
            // 一直扩张右边界，将右边界的值加入滑动窗口中
            int rIndex = s.charAt(r) - 'A';
            hash[rIndex]++;
            // 计算当前窗口中最右边元素的数量，判断是否大于最大数量
            max = Math.max(max, hash[rIndex]);
            // 如果窗口的大小减去窗口中的最多元素的数量大于k，那么不能继续扩大窗口了，需要左边界右移
            if (r - l + 1 - max > k) {
                int lIndex = s.charAt(l) - 'A';
                // 左边界右移时，删除窗口中左边界的元素
                hash[lIndex]--;
                // 左边界右移一个
                l++;
            }
            // 右边界始终右移
            r++;
        }
        // 因为左右边界考虑了k所以直接返回左边界的位置-左边界的位置
        return r - l;
    }
}

参考文献

官方题解

class Solution {
    public int characterReplacement(String s, int k) {
        int[] num = new int[26];
        int n = s.length();
        int maxn = 0;
        int left = 0, right = 0;
        while (right < n) {
            num[s.charAt(right) - 'A']++;
            maxn = Math.max(maxn, num[s.charAt(right) - 'A']);
            if (right - left + 1 - maxn > k) {
                num[s.charAt(left) - 'A']--;
                left++;
            }
            right++;
        }
        return right - left;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement/solution/ti-huan-hou-de-zui-chang-zhong-fu-zi-fu-n6aza/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信