Code & Func

第6天，下雨了。。。。

今天的题目是Longest Repeating Character Replacement。

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

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

为了解决这个问题，我增加了一次判断，对前k个字符进行替换，替换成下一个字符，即以下一个字符为目标，计算修改k次后能达到的长度。

具体代码如下：

1
class Solution {
2
public:
3
    int characterReplacement(string s, int k) {
4
        int len = s.size();
5
        int res = 0;
6
        int j, a;
7
        for(int i = 0; i < len; i++) {
8
            char c = s[i];
9
            a = k;
10
            for(j = i+1;j < len; j++) {
11
                if (c != s[j]) {
12
                    if (a == 0) break;
13
                    else a--;
14
                }
15
            }
18 collapsed lines
16
            res = max(j-i, res);
17
        }
18

19
        for(int i = 0;i < k && i+1 < len; i++) {
20
            char c = s[i+1];
21
            a = k-i-1;
22
            for(j = i + 2;j < len; j++) {
23
                if (c != s[j]) {
24
                    if (a == 0) break;
25
                    else a--;
26
                }
27
            }
28
            res = max(j-i, res);
29
        }
30

31
        return res;
32
    }
33
};

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

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

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

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

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

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