[Leetcode 424] Longest Repeating Character Replacement

作者 Shilei Tian 日期 2017-01-06
[Leetcode 424] Longest Repeating Character Replacement

题目要求

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:

Both the string’s length and k will not exceed $10^4$.

Example 1:

Input:

s = “ABAB”, k = 2

Output:

4

Explanation:

Replace the two ‘A’s with two ‘B’s or vice versa.

Example 2:

Input:

s = “AABABBA”, k = 1

Output:

4

Explanation:

Replace the one ‘A’ in the middle with ‘B’ and form “AABBBBA”.

The substring “BBBB” has the longest repeating letters, which is 4.

解题思路

这道题目拿到手以后,想到的思路是从第一个元素开始起,判断用掉 k 次后能够构建多长的符合题目要求的子串。那下一个问题是,如何判断最长能够构建多长呢?这个就是问题的核心了。因为我们无法提前知道从第一个元素开始我们能够通过 k 次变换产生多长的连续元素,因此我们没有办法先统计哪个元素出现的次数最多。但是我们可以这样,用 i 标记开始元素的位置,j 标记我们最长能够构建到的那个元素的位置,刚开始令 j 等于 i(当然,也可以等于 i + 1),每次我们统计从第 i 个元素到第 j 个元素之间出现次数最多的那个元素出现的次数,记为 c,那么 j - i - c 就是我们想要将这些元素变成一样的元素所需要进行变换的最少次数。每次对 j 进行自增,然后求一下 c,如果 j - i - c = k,那么这个 j 就是从第 i 个元素开始,经过 k 次变换后能够构成的最长的重复元素子串。

上面的思路是没有错的,但是效率还是稍微差了一些,这个时候就需要了解一下类似计算机网络中滑动窗口的概念了。咱们这里只讲在这道题里面是如何体现的。将从第 i 个元素开始,到那个经过最多 k 次变换可以生成一个重复子串的最远位置 j,这之间所有的元素我们组成了一个滑动窗口。题给例子 Example 2 如下图所示:

滑动窗口示意图

上图中,红色框代表滑动窗口,每次窗口的大小不一样。黄色的代表需要进行变换的元素。我们可以看到,当 i = 0 时,当我们只能变换一个元素时,窗口的大小为 4,亦即我们最多可以得到一个长度为 4 的重复串,变换 2 号元素。当 i = 1 时,此时 j 还是等于 3,因为变换还会时 2 号元素。以此类推,我们可以最终得到最长的重复子串的长度就是 4

如何提高效率呢?考虑我们是如何得到滑动窗口的大小的?是通过计算 ij 之间的元素中出现最多的那个出现的次数 c,然后用 j - i 去减掉它,就得到我们需要进行变换的次数。那么每次我们 i 向前滑动一个的时候,对 j - i - c 造成的影响,就是第 i 号元素出现的次数减少了一次,那么我们只需要将第 i 号元素出现的次数减少一次以后,重新计算 j - i - c,如果这个值小于 k,那么我们的 j 还可以继续向前滑动,重复此前的过程;如果等于 k,那么我们就又能得到一个连续子串,但是这个子串的长度肯定小于刚才的那个,因为我们的 i 向前滑动了。

具体的代码如下:

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
class Solution {
public:
int characterReplacement(string s, int k) {
count.assign(26, 0);
int _max = 0;
for (int i = 0, j = 0; i < s.size(); ++i) {
while (getDifferent() <= k && j < s.size()) {
count[s[j] - 'A']++;
if (getDifferent() > k) {
count[s[j] - 'A']--;
break;
}
++j;
}
_max = max(j - i, _max);
count[s[i] - 'A']--;
}
return _max;
}

private:
vector<int> count;

int getDifferent() {
int sum = 0, _max = 0;
for (auto e : count) {
sum += e;
_max = max(_max, e);
}
return sum - _max;
}
};