Longest Repeating Character Replacement

LeetCode

第6天， 下雨了。。。。

今天的题目是Longest Repeating Character Replacement。

emmmm，这道题一开始的解法虽然AC了，但是时间复杂度是O(n^2)，但是最佳解法却是O(n)，先看下我的解法：

思路比较简单，就是不断以某个字符为起始，以这个字符为目标，计算修改k次后能达到的长度，然而这样会有个问题，例如ABBB,如果k为1的话，我计算出来是3，但真实结果是4。

为了解决这个问题，我增加了一次判断，对前k个字符进行替换，替换成下一个字符，即以下一个字符为目标，计算修改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
class Solution {
public:
    int characterReplacement(string s, int k) {
        int len = s.size();
        int res = 0;
        int j, a;
        for(int i = 0; i < len; i++) {
            char c = s[i];
            a = k;
            for(j = i+1;j < len; j++) {
                if (c != s[j]) {
                    if (a == 0) break;
                    else a--;
                }
            }
            res = max(j-i, res);
        }
        
        for(int i = 0;i < k && i+1 < len; i++) {
            char c = s[i+1];
            a = k-i-1;
            for(j = i + 2;j < len; j++) {
                if (c != s[j]) {
                    if (a == 0) break;
                    else a--;
                }
            }
            res = max(j-i, res);
        }
        
        return res;
    }
};

OK，现在可以忽略掉上面的解法了，看看O(n)的解法是怎样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> ch(26);
        int start = 0, end = 0, max_count = 0;
        int len = s.size();
        while(end < len) {
            ch[s[end] - 'A']++;
            // update max_count
            max_count = max(max_count, ch[s[end]-'A']);
            end++;
            if ( end - start > max_count + k) {
                ch[s[start] - 'A']--;
                start++;
            }
        }
        return end - start;
    }
};

很精妙的用滑窗解决了这个问题：

首先，它用一个数组记录滑窗内的出现字符的个数，因此每次迭代或操作都向前移动一个字符而已，所以我们可以很容易维护出一个max_count，即所有字符出现次数最大的那一个。

然后如果是一个正确的解的话，要满足一个约束end - start - k > max_count,如果满足的话，可以增大滑窗去寻找更大的窗口，如果不行，那么我们就向前移动滑窗。

虽然在迭代结束后，我们不能保证当前滑窗就是满足约束的解，但是我们可以保证，最大的窗口大小一定和我们现在的滑窗大小是一样的，故可以得到解。