给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。
注意:字符串长度 和 k 不会超过
。
示例 1:
输入:s = "ABAB", k = 2
输出:4
解释:用两个'A'替换为两个'B',反之亦然。
示例 2:
输入:s = "AABABBA", k = 1
输出:4
解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
令 l
为符合条件的子串的左端点,r
为符合条件的子串的右端点。
使用 cnt
统计 [l,r]
范围的子串中每个字符串出现的次数。
对于合法的子串而言,必然有:
sum(所有字符的出现次数) - max(出现次数最多的字符的出现次数)= other(其他字符的出现次数) <= k
。
当找到这样的性质之后,我们可以对 s
进行遍历,每次让 r
右移并计数,如果符合条件,更新最大值;如果不符合条件,让 l
右移,更新计数,直到符合条件:
class Solution {
public int characterReplacement(String s, int k) {
char[] cs = s.toCharArray();
int[] cnt = new int[26];
int ans = 0;
for (int l = 0, r = 0; r < s.length(); r++) {
// cnt[cs[r] - 'A']++;
int cur = cs[r] - 'A';
cnt[cur]++;
// while (!check(cnt, k)) cnt[cs[l++] - 'A']--;
while (!check(cnt, k)) {
int del = cs[l] - 'A';
cnt[del]--;
l++;
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
boolean check(int[] cnt, int k) {
int max = 0, sum = 0;
for (int i = 0; i < 26; i++) {
max = Math.max(max, cnt[i]);
sum += cnt[i];
}
return sum - max <= k;
}
}
l
和 r
指针对 s
进行单次扫描,复杂度为 ;check
方法是对长度固定的数组进行扫描,复杂度为
。整体复杂度为
。
之所以有这个环节,是因为今天将题解发到 LeetCode 的时候,有同学对该题的时间复杂度分析提出了疑问。
估计也是部分同学的疑惑,所以干脆拎出来讲讲 ~
我整理了一下,留言内容大致为:
。 首先是最外部 for 循环更新 right 指针,又有一个 while 循环,while 循环条件中又嵌套了一个 check 函数,这个函数里又有 for 循环。
(严格来说是
,忽略常数后是
),而不是
,因为不是每次 right 走一步,left 就要扫描一遍。 而 check 是固定扫描一个长度为 26 的数组,可以看做是一个
的操作,不随着样本数量的增大的变化的(也就是不随着 字符串 s 的长度变化而变化),忽略常数后是
的。 因此整体复杂度是 O(n) 的。
这才是正确的复杂度分析方式。通过这个例子,希望你能有所体会。
这是我们「刷穿 LeetCode」系列文章的第 No.*
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 */1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。