题目描述
给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。
注意:字符串长度 和 k 不会超过$10^4$。
样例
输入:s = "ABAB", k = 2
输出:4
解释:用两个'A'替换为两个'B',反之亦然。
输入:s = "AABABBA", k = 1
输出:4
解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
模板题
最长连续不重复子序列
与本题非常相似,墙裂推荐先刷模板题!!
算法1
(暴力枚举) $O(n^3)$
虽然会TLE, 但是古人云:遇事不决,暴力美学
枚举所有子串,对每一个子串:
1. 如果所有字符相同,则枚举更长的子串
2. 如果有不同的字符,则k–去替换出现次数最多字符以外的字符
分析得知,暴力算法枚举所有子串,而子串之间有很多重叠包含
时间复杂度
枚举子串 $O(N^2)$
对每一个子串计算结果 $O(N)$
总体 $O(N^3)$
C++ 代码
略
算法2
(双指针) $O(n)$
基于对暴力算法的分析,我们发现一个重要问题是它为了枚举所有子串,大量重复地枚举了右边界,事实上我们可以不断递增右边界(扩展边界),当扩展的区间不满足条件时,就递增左边界(收缩边界)
考虑维护一个区间[j, i]
, 这个区间满足:最少替换k个字符后,所有字符均相同。我们希望这个区间尽可能大,因此要尽可能地扩展区间(i++
),但当区间不满足条件时又要收缩区间(j++
)。那么,什么时候需要收缩区间呢?
答案就是,如果当前区间在替换k个字符后仍含有不同字符,则必须收缩区间,才能满足条件(反证法可证)。
这就意味着,左右边界只会不断增大,因此不必重复枚举右边界;
另外,在计算最大区间时,我们可以维护一张哈希表,它记录了当前区间每个字母的数量。有了这张哈希表,我们就能维护一个变量maxCount,它的含义是:_历史_区间中数量最多的字符数。
maxCount + k可以当作是当前区间的最大长度(严格意义上来说并不是,因为maxCount是对历史区间而言的,但是由于这道题是求最大值,因此答案不会错过,之所以用maxCount是因为当前区间的最大长度不好维护), 它如果小于当前区间的长度,则需要收缩区间。
时间复杂度
i
, j
分别只枚举了$n$次,因此总体时间复杂度O($N$)
C++ 代码
class Solution {
public:
int characterReplacement(string s, int k) {
vector<int> hash(26,0);
int n = s.size();
if(!n) return 0;
int maxCount = 0;
int ans = 0;
for(int i = 0, j = 0; i < n; i ++){
hash[s[i]-'A'] ++;
maxCount = max(maxCount, hash[s[i]-'A']);
while(maxCount + k < i - j + 1){
hash[s[j] - 'A'] --;
j ++;
}
ans = max(ans, i - j + 1);
}
return ans;
}
};