LeetCode424-替换后的最长重复字符

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/longest-repeating-character-replacement/

中文链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement/

题目详述

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

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

示例 1:

1
2
3
4
5
6
7
8
输入:
s = "ABAB", k = 2

输出:
4

解释:
用两个'A'替换为两个'B',反之亦然。

示例 2:

1
2
3
4
5
6
7
8
9
输入:
s = "AABABBA", k = 1

输出:
4

解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

题目详解

  • 滑动窗口，本题类似于 LeetCode76-最小覆盖字串。区别在于：
    • 本题找到一个满足条件的区间很容易，当不满足时需要调整区间使满足条件。从更新结果角度来看，是在 while 循环外更新结果，结果是满足条件的最长区间。
    • LeetCode76-最小覆盖字串 找到一个满足条件的区间不容易，当找到一个满足条件条件的区间才更新结果，并找到所有满足条件的区间同时更新结果，直到又不满足条件，然后寻找下一个满足条件的区间。从更新结果角度来看，是在 while 循环内更新结果，结果是满足条件的最短区间。
  • 题目说明字符串仅由大写英文字母。可以遍历所有大写字母，统计与当前字母不同的个数，若大于 k 则调整区间直至区间满足条件。
  • 时间复杂度为 o(26n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode_00424 {

    public int characterReplacement(String s, int k) {
        char[] cs = s.toCharArray();
        int res = 0;
        for (char c = 'A'; c <= 'Z'; ++c) {
            int cnt = k;
            int l = 0, r = 0;
            while (r < cs.length) {
                if (cs[r++] != c) {
                    --cnt;
                    while (cnt < 0) {
                        if (cs[l++] != c) {
                            ++cnt;
                        }
                    }
                }
                res = Math.max(res, r - l);
            }
        }
        return res;
    }
}
  • 也可以直接统计区间区间内同种字符出现次数最多的个数，剩下的就是其他字符，当其他字符个数大于 k 则调整区间直至区间满足条件。
  • 时间复杂度为 o(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00424 {

    public int characterReplacement(String s, int k) {
        char[] cs = s.toCharArray();
        int[] map = new int[26];
        int res = 0;
        int max = 0;
        for (int l = 0, r = 0; r < cs.length; ) {
            max = Math.max(max, ++map[cs[r++] - 'A']);
            while (r - l - max > k) {
                --map[cs[l++] - 'A'];
            }
            res = Math.max(res, r - l);
        }
        return res;
    }
}