【Leetcode】424.替换后的最长重复字符

424. 替换后的最长重复字符

题目

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

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

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

方法一（滑动窗口）

要判断能否将一个子串替换k次以得到一个只包含重复字母的子串，只需要判断该子串中除了出现最多次的那个字符外的其他字符出现的总次数是否大于k即可。大于k则不可，小于k则可。

用left和right这两个指针分别指向滑动窗口的左端和右端。

right不断向右移动，每次都在当前窗口后再添加一个新的字符，看看窗口是否还能继续满足要求。

  • 如果窗口内除出现次数最多的字符外的其他字符出现的总次数大于k了，则该窗口不能满足要求了，left要向右移动。
  • 否则，该窗口满足要求，用当前窗口的长度更新最大值res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int characterReplacement(String s, int k) {
    //用桶来记录当前窗口中的字符以及其出现的次数
    int[] buckets = new int[26];
    int res = 0;
    //left和right分别记录滑动窗口的两端
    int left = 0;
    int right = 0;
    int maxCount = 0;  //maxCount记录当前窗口内出现最多的那个字符出现的次数
    while(right < s.length()){
        //无论是左端还是右端，只要窗口移动了，就要更新maxCount
        buckets[s.charAt(right) - 'A']++;
        maxCount = Math.max(maxCount, buckets[s.charAt(right) - 'A']);
        while(right - left + 1 - maxCount > k){
            buckets[s.charAt(left) - 'A']--;
            left++;
            for(int i = 0; i < 26; i++)
                maxCount = Math.max(maxCount, buckets[i]);
        }
        res = Math.max(res, right - left + 1);
        right++;
    }
    return res;
}
  • 时间复杂度：O(26n)
  • 空间复杂度：O(1)

方法二（改进）

在方法一中，窗口左端点left每移动一次，就要遍历一次桶以更新maxCount，效率不高。

因此我们采取如下改进方法：

对于滑动窗口，只允许两种操作：

  • 扩展：right右移，left不动
  • 平移：right和left同时右移

因为题目让我们求的是长度，而不是具体的子串。因此我们可以用滑动窗口的窗口大小来记录答案。

  • 右移时，窗口大小加1
  • 平移时，窗口大小不变

还是像方法一一样，right不断右移，每次尝试着将一个新的字符加入窗口。如果加入后窗口符合要求，那么扩展窗口。如果加入后窗口不符合要求，那么平移窗口。因为窗口的大小永远不可能减小，所以遍历结束后，当前窗口大小就是符合条件的最大窗口大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int characterReplacement(String s, int k) {
    int[] buckets = new int[26];
    int left = 0;
    int right = 0;
    int maxCount = 0;  
    while(right < s.length()){
        buckets[s.charAt(right) - 'A']++;
        maxCount = Math.max(maxCount, buckets[s.charAt(right) - 'A']);
        if(right - left + 1 - maxCount > k){
            buckets[s.charAt(left) - 'A']--;
            left++;
        }
        right++;
    }
    return right - left;
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)