LeetCode 424. Longest Repeating Character Replacement

思路很重要。
给定一个长度n的字符串s和限制k，将s中的部分字符替换(替换次数<=k)后，能得到连续字符（如AAAA）的长度最大为多少？
使用滑动窗口的思路可以在O(n)时间复杂度的情况下解决这个问题。需要记录当前窗口内各个字符的计数值（可以看做分布情况）以及当前窗口的起始点，窗口内最多字符的计数best。我们知道，最多字符的计数best+修改数量k如果还是不能使得当前窗口内的字符都统一的话，就得把窗口缩小（起始点后挪）。窗口缩小时记得把窗口计数更新一下。
这里有一个tricky的地方，best值本来在滑动窗口的时候是要更新的，因为可能窗口过了这个best会变小。但是由于我们要找的只是个最优的值，所以这个情况并不需要考虑对best进行更新，反正它也成不了最优。

代码

class Solution {
public:
    int characterReplacement(string s, int k) {
        //sliding window solution
        int charCount[26] = {0};
        int w_start = 0, best = 0;
        for(int w_end = 0; w_end < s.size(); w_end++){
            charCount[s[w_end]-'A']++;
            best = max(best, charCount[s[w_end]-'A']);
            if(best+k <= w_end-w_start){
                //replace k chars in current window,
                // if we still can't have the optimal
                // we will shrink the left border of window
                charCount[s[w_start]-'A']--;
                w_start++;
            }
        }
        return s.size()-w_start;
    }
};