LCP-424 替换后的最长重复字符

题目回顾

解法思路

本题采用滑动窗口双指针的思路来进行解题。(太久没做题了,标准题解看来半天才看懂)

从题目的要求来分析其实很好理解。要求最长的子串,那么肯定这个串是连续的(废话),所以就很适合用滑动窗口的方法,一个窗口从左移到右,寻找出符合条件的最大窗口长度,即为题目所求。本题的关键就在于如何控制窗口左右边界的移动。

先来看看怎样的窗口子串是符合条件的:要找到尽可能长的重复串,毋庸置疑,肯定是找出现次数最多的字母,同时你还可以最多把k的其他字符也变成它。所以符合条件的子串一定满足:

1
窗口长度 - 同一字母最大出现次数 <= k

窗口移动的规则即为:

  • 右指针++
  • 若区间内窗口长度 - 同一字母最大出现次数 > k左指针++

以上操作保证了窗口长度只增不减,这样最后的窗口长度就是结果

比如那s = "AABABBA", k = 1的例子

初始时左右指针都指向0

AABABBA


窗口长度(1) - 1 < 1,r++

AABABBA


窗口长度(2) - 2 < 1,r++

AABABBA

​ ↑


窗口长度(3) - 2 <= 1,r++

AABABBA

​ ↑


窗口长度(4) - 3 <= 1,r++

AABABBA

​ ↑


窗口长度(5) - 3 > 1,r++, l++

AABABBA

​ ↑


窗口长度(5) - 3 > 1,r++, l++

​ ↓

AABABBA

​ ↑

最终结果为 $r-l = 4$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
* @lc app=leetcode.cn id=424 lang=java
*
* [424] 替换后的最长重复字符
*/

class Solution {
public int characterReplacement(String s, int k) {

int[] cnt = new int[26];

int l = 0;
int r = 0;
int maxn = 0; // 窗口内出现最多次的字母个数
for (; r < s.length(); r++) {
cnt[s.charAt(r)-'A']++;
maxn = Math.max(maxn, cnt[s.charAt(r)-'A']);
if(r-l+1-maxn>k){
cnt[s.charAt(l)-'A']--; // 窗口最左边的字符出去了
l++;
}
}
return r-l;
}
}

时间复杂度O(n),空间复杂度O(|M|)

LCP-424 替换后的最长重复字符

https://blog.luzy.top/posts/1594990787/

作者

江风引雨

发布于

2021-02-02

更新于

2023-01-10

许可协议

CC BY 4.0

评论