本文共 1398 字，大约阅读时间需要 4 分钟。

题目描述

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

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

示例 1：

输入：s = “ABAB”, k = 2

输入：s = “AABABBA”, k = 1

解题思路

• 右边界先移动找到一个满足题意的可以替换 k 个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下；

• 然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串；

• 替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。

class Solution_424 {       public int characterReplacement(String s, int k) {           int len = s.length();        if (len < 2){               return len;        }        char[] charArray = s.toCharArray();        //左右边界都从头开始        int left = 0;        int right = 0;        int res = 0;        int maxCount = 0;        int[] freq = new int[26];        // [left, right) 内最多替换 k 个字符可以得到只有一种字符的子串        while (right < len){               freq[charArray[right] - 'A']++;            // 在这里维护 maxCount，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加            maxCount = Math.max(maxCount,freq[charArray[right] - 'A']);            right++;            if (right - left > maxCount + k){                   // 说明此时 k 不够用                // 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动                // 移出滑动窗口的时候，频数数组须要相应地做减法                freq[charArray[left]-'A']--;                left++;            }            res = Math.max(res,right-left);        }        return res;    }}