题目描述

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

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

示例 1：

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

示例 2：

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

题解思路

果然是简单题我重拳出击,中等题我唯唯诺诺

好吧这题我不会,以下为大佬的答案

• 本题是比较典型的滑动窗口问题
• 这类问题一般通过一个滑动窗口就能在 O(N)O(N) 的时间复杂度下求解.

本题可以先退化成考虑K=0的情况，此时题目就变成了求解字符串中最长连续子串长度问题了。
我们先可以通过这个特例先了解一下滑动窗口的求解过程

上图的求解过程展示中，窗口从左至右不断扩张/滑动，当窗口触达字符串末尾字符时，运算结束，窗口的宽度为最终结果。初始窗口的宽度为 1，我们不断的通过向当前窗口覆盖的子串后面追加一个字符看是否能满足我们的要求，如果满足窗口扩张，如果不满足，窗口向右滑动。

当 K>0 时，子串的条件变成了允许我们变换子串中的 KK 个字符使其变成一个连续子串

那么这个题的关键点就是我们如何判断一个字符串改变 KK 个字符，能够变成一个连续串

如果当前字符串中的出现次数最多的字母个数 +K+K 大于串长度，那么这个串就是满足条件的

我们维护一个数组 int[26] 来存储当前窗口中各个字母的出现次数，leftleft 表示窗口的左边界，rightright 表示窗口右边界

• 窗口扩张：不变，
• 窗口滑动：，

historyCharMax 保存滑动窗口内相同字母出现次数的 历史 最大值，通过判断窗口宽度 (right - left + 1)(right−left+1) 是否大于 historyCharMax + K 来决定窗口是否做滑动，否则窗口就扩张。

Sulution

class Solution {
    private int[] map = new int[26];

    public int characterReplacement(String s, int k) {
        if (s == null) {
            return 0;
        }
        char[] chars = s.toCharArray();
        int left = 0;
        int right = 0;
        int historyCharMax = 0;
        for (right = 0; right < chars.length; right++) {
            int index = chars[right] - 'A';
            map[index]++;
            historyCharMax = Math.max(historyCharMax, map[index]);
            if (right - left + 1 > historyCharMax + k) {
                map[chars[left] - 'A']--;
                left++;
            }
        }
        return chars.length - left;
    }
}

答案作者：migoo
链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement/solution/tong-guo-ci-ti-liao-jie-yi-xia-shi-yao-shi-hua-don/

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