问题描述
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意：字符串长度 和 k 不会超过 104。
示例 1：
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。
示例 2：
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
解题思路
因为 \(n\le10^4\)，所以可能至少需要 \(n^2\) 复杂度或以下的算法。
题目的意思是要找到一个区间 \([l,r]\)，其中出现最多的字符数量加上 \(k\) 大于等于该区间的长度，求满足这样条件的最大区间长度。
方法一：枚举（超时）
因为是求区间，暴力的话可以枚举所有的区间。
因为要知道某个区间哪个字符出现的次数最多，所以用字母出现次数前缀和数组来记录每个字符出现的次数。
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
26
27
28
29
30
31
32
33
34
35
36 | class Solution {
public:
int characterReplacement(string s, int K) {
int n = s.size();
vector<vector<int>> count(26, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
if (i) (count[j][i] = count[j][i - 1]);
}
++count[s[i] - 'A'][i];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = n - 1; j >= i; --j) { // 反向遍历优化
int mx = 0;
for (int k = 0; k < 26; ++k) {
mx = max(mx, i ? count[k][j] - count[k][i - 1] : count[k][j]);
}
int w = j - i + 1;
if (mx + K >= w) {
ans = max(ans, w);
break;
}
}
}
return ans;
}
};
|
时间复杂度：\(\mathcal{O}(n^2)\)
空间复杂度：\(\mathcal{O}(26n)\)
方法二：二分（通过）
既然 \(\mathcal{O}(n^2)\) 的方法超时，那么可以尝试 \(\mathcal{O}(n\log n)\) 的方法。
\(\mathcal{O}(n\log n)\) 的方法最容易想到的就是二分，这里同样使用了前缀和数组预处理了字母出现次数。
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39 | class Solution {
public:
int characterReplacement(string s, int K) {
int n = s.size();
vector<vector<int>> count(26, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
i && (count[j][i] = count[j][i - 1]);
}
++count[s[i] - 'A'][i];
}
auto ok = [&s, &count, n, K] (int w) {
for (int i = 0; i + w - 1 < n; ++i) {
int k = i + w - 1;
int mx = 0;
for (int j = 0; j < 26; ++j) {
mx = max(mx, i ? count[j][k] - count[j][i - 1] : count[j][k]);
}
if (mx + K >= w) return true;
}
return false;
};
int L = 0, R = n;
while (L < R) {
auto M = L + ((R - L + 1) >> 1);
if (ok(M)) L = M;
else R = M - 1;
}
return L;
}
};
|
时间复杂度：\(\mathcal{O}(26n\log n)\)
空间复杂度：\(\mathcal{O}(26n)\)
方法三：双指针（通过）
要求满足条件的最大的 \([l,r]\) 区间，我们可以首先固定左端点，看右端点最远能够到达的地方。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
public:
int characterReplacement(string s, int k) {
int n = s.size();
vector<int> count(26);
int ans = 0, mx = 0;
for (int L = 0, R = 0; R < n; ++R) {
int idx = s[R] - 'A';
++count[idx];
mx = max(mx, count[idx]);
while (k + mx < R - L + 1) {
--count[s[L++] - 'A'];
}
ans = max(ans, R - L + 1);
}
return ans;
}
};
|
时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(26)\)