LeetCode_424_替换后的最长重复字符

题目链接

• https://leetcode.cn/problems/longest-repeating-character-replacement/

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 10^5
• s 仅由大写英文字母组成
• 0 <= k <= s.length

解题思路

双指针滑动窗口法

可以先退化成考虑K=0的情况，此时题目就变成了求解字符串中最长连续子串长度的问题了。如下图所示

• 窗口从左到右不断扩张/滑动，当窗口到了字符串末尾字符时，运算结束，窗口的宽度就是最终结果。

• 初始窗口的宽度为1，我们不断的通过向当前窗口覆盖的子串后面追加一个字符看是否能满足我们的要求，如果满足窗口扩张，如果不满足，则窗口向右滑动。

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

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

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

• 因此使用一个数组int[]record = new int[26]来存储当前窗口中各个字母的出现次数,left和right表示左右边界

  • 窗口扩张：left不变，right++
  • 窗口滑动：left++,right++

• max保存滑动窗口内相同字母出现次数的历史最大值，通过判断窗口宽度right - left + 1 > max + k来决定窗口是滑动还是扩张

AC代码

class Solution {
    public int characterReplacement(String s, int k) {
        if (s == null) {
            return 0;
        }
        char[] s1 = s.toCharArray();
        int len = s.length();
        int[] record = new int[26];
        int left = 0;
        int right = 0;
        int max = 0;
        for (right = 0; right < len; right++) {
            record[s1[right] - 'A']++;
            max = Math.max(max, record[s1[right] - 'A']);
            if ((right - left + 1) > max + k) {
                record[s1[left] - 'A']--;
                left++;
            }
        }
        return len - left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22