替换后的最长重复字串

发表于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

LeetCode每日一题，424. Longest Repeating Character Replacement

先看题目描述

ymTAZn.png

大意就是给定一个字符串 s 和一个整数 k，我们可以把 s 中至多 k 个字母替换成任意字母，让我们返回替换后的最长重复子串长度

算法和思路

滑动窗口

这题也是看题解才会的

我们维护一个数组 cnt[26] 来保存滑动窗口内各字母的出现次数，maxCount 表示当前滑动窗口中出现最多的字母次数，left 表示滑动窗口的左边界(闭区间)，right 表示滑动窗口的右边界(开区间)，通过判断滑动窗口长度 right - left 是否大于 maxCount + k 来判断滑动窗口该扩张还是右移

  • 若 right - left > maxCount + k，说明此时以 left 为左端点，长度为 right - left 的子串不满足条件，则将滑动窗口右移
  • 否则，说明此时以 left 为左端点，长度为 right - left 的子串满足条件，则扩张滑动窗口

最后返回滑动窗口的长度即可

算法源码

滑动窗口

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

            if ((right - left) > maxCount + k) {
                cnt[cs[left] - 'A']--;
                left++;
            }
        }
        return right - left;
    }
}

感觉自己没怎么做过滑动窗口的题目，对滑动窗口如何使用不太熟悉，通过此题了解了一点滑动窗口的用法，个人感觉滑动窗口问题的关键在于对何时扩张滑动窗口，何时移动滑动窗口进行判断