[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.

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个字母之后能组成的相同字母的子串的长度，所以思路还是偏向滑动窗口（sliding window）。那么替换字母的原则应该是先统计目前每个不同字母的出现次数，然后用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是凑不到一起的。

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

时间O(n)

空间O(1) - 一个26位长度的数组

Java实现

 1 class Solution {
 2     public int characterReplacement(String s, int k) {
 3         int[] map = new int[128];
 4         int start = 0;
 5         int end = 0;
 6         int res = 0;
 7         int max = 0;
 8         while (end < s.length()) {
 9             char c1 = s.charAt(end);
10             map[c1]++;
11             max = Math.max(max, map[c1]);
12             if (end - start + 1 - max > k) {
13                 char c2 = s.charAt(start);
14                 map[c2]--;
15                 start++;
16             }
17             res = Math.max(res, end - start + 1);
18             end++;
19         }
20         return res;
21     }
22 }

JavaScript实现

 1 /**
 2  * @param {string} s
 3  * @param {number} k
 4  * @return {number}
 5  */
 6 var characterReplacement = function(s, k) {
 7     let count = {};
 8     let start = 0;
 9     let max = 0;
10     let res = 0;
11     for (let end = 0; end < s.length; end++) {
12         count[s[end]] = count[s[end]] + 1 || 1;
13         max = Math.max(max, count[s[end]]);
14         if (end - start + 1 - max > k) {
15             count[s[start]]--;
16             start++;
17         }
18         res = Math.max(res, end - start + 1);
19     }
20     return res;
21 };

sliding window相关题目

LeetCode 题目总结

[LeetCode] 424. Longest Repeating Character Replacement

推荐阅读