[LeetCode] 424. Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:
Input: s = “ABAB”, k = 2
Output: 4
Explanation: Replace the two ‘A’s with two ‘B’s or vice versa.

Example 2:
Input: s = “AABABBA”, k = 1
Output: 4
Explanation: Replace the one ‘A’ in the middle with ‘B’ and form “AABBBBA”.
The substring “BBBB” has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

Constraints:
1 <= s.length <= 105
s consists of only uppercase English letters.
0 <= k <= s.length

替换后的最长重复字符。

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

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

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

思路

题意是给一个字符串，只有大写字母，允许你替换其中的 k 个字母，问替换操作完成后能返回的最长字母相同的子串的长度是多少。既然是看替换 k 个字母之后能组成的相同字母的子串的长度，所以思路还是偏向滑动窗口。那么替换字母的原则应该是先统计目前每个不同字母的出现次数，然后用 k 尽量去替换成那个出现最多次数的字母，看看是否能组成最长的子串。具体做法如下

• 创建一个 map 记录 s 中每个字母和他们的出现次数
• 创建两个指针 start 和 end 准备卡住窗口
• end 先移动，并同时用一个变量 max 找到当下最大的出现次数
• 如果当前窗口 size - k > max，则考虑缩小窗口尺寸，挪动 start 指针
• 窗口 size 缩减到小于 max + k 之后，记录一个当前窗口的值，这个值就是替换了 k 个字符之后能组成的最长重复子串的长度

这个题我在做的时候有个疑问，为什么通过滑动窗口找到的这个最长子串的长度是对的呢？我举了个反例，比如 s 是 ABCDEFGA 好了，k = 2，出现次数最多的字母依然是 A。按照上面的算法，直到扫到 input 的最后才会发现出现次数最多的字母是 A，既然 k 是 2，所以无论你替换别的任何字母，最后跟 A 凑成最长的子串都一定是 1 + 2 = 3，因为前后两个 A 是凑不到一起的。

这个例子只能证明滑动窗口可以解决这道题，并没有回答另一个疑问：最长的子串里面一定包含出现次数最多的字母，这个没有什么疑问。但是左指针在往前走，试图缩短窗口尺寸的时候，会不会造成额外的问题？答案是不会。我参考了这个帖子。右指针停下的位置一定是当前出现次数最多的字母的位置。如果此时左指针开始往前走（试图缩短窗口尺寸），虽然随着左指针往前走，出现次数最多的字母的次数（最多次数）会被减少，但是并不影响这个字母是出现次数最多的字母的事实。目前需要找的窗口大小依然是基于这个出现次数最多的字母而找的。

第三个疑问是按照代码里跑的方式，start 和 end 指针中间也许不会包含出现次数最多的那个字母所有出现的地方，比如我们发现 max = 5，但是 start 和 end 之间也许并不会包含那个字母 5 次，这种情况下，代码是让 start 和 end 指针同时往前走的，只要两个指针的距离没变，结果就是对的。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int characterReplacement(String s, int k) {
        int res = 0;
        int start = 0;
        int end = 0;
        int max = 0;
        int[] map = new int[256];
        while (end < s.length()) {
            char c1 = s.charAt(end);
            map[c1]++;
            max = Math.max(max, map[c1]);
            end++;
            while (end - start - max > k) {
                char c2 = s.charAt(start);
                map[c2]--;
                start++;
            }
            res = Math.max(res, end - start);
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
	let count = {};
	let start = 0;
	let max = 0;
	let res = 0;
	for (let end = 0; end < s.length; end++) {
		count[s[end]] = count[s[end]] + 1 || 1;
		max = Math.max(max, count[s[end]]);
		if (end - start + 1 - max > k) {
			count[s[start]]--;
			start++;
		}
		res = Math.max(res, end - start + 1);
	}
	return res;
};