Leetcode424.替换后的最长重复字符

点我(^_^)

给定一个字符串 s，你可以最多替换其中 k 个字符为任意字符，返回替换后的字符串中最长重复字符子串的长度。

最初写这道题时，没有想到官方的最优解，只是想到一种 O(26*s) 时间复杂度的解法。
类似于双指针，这里复杂度里的 26 代表每次只替换成一个字母，遍历一遍字符串更新答案，比如第一次只替换字母为 A，那么右指针一直往右移，如果是 A 那么不用替换，当前子串长度+1；如果不是 A 那么需要替换，如果替换次数还有，那么替换次数-1，当前子串长度+1；如果没有替换次数了，那么左指针移动到最先被替换的位置的下一个位置，这时子串长度就为 right - left + 1。那么这个最先被替换的位置可以使用队列维护，队首元素就是最先被替换的位置，左指针移动后队首元素弹出。每次移动右指针完尝试用当前子串长度更新答案。

class Solution {
public:
    int characterReplacement(string s, int k) {
        int ans = 0;
        for(int i=0; i<26; ++i)
        {   
            queue q;
            int now = k;
            int len = 0;
            for(int j=0; j
                if(s[j]-'A' != i)
                {
                    if(now != 0)
                    {
                        q.push(j);
                        now --;
                        // cout<
                        if(q.empty())
                        {
                            len = 0;
                            continue;
                        }
                        int pos = q.front();
                        q.pop();
                        len = j - pos - 1;
                        q.push(j);
                        // cout< 
解题思路(官方) 
官方解法也是使用双指针，时间复杂度为 O(s)。
 维护一个当前子串中，最多重复元素的个数maxn；维护一个字符数组，代表每个字符的在当前子串中的个数。根据 maxn，我们就能判断出当前除了最多重复元素之外的其他元素个数是多少，即当前子串长度 right - left + 1 - maxn，如果该值大于 k，那么左指针需要向右移动一格，然后右指针再向后移动，重复上述操作，虽然可能会出现非最多重复元素的个数大于 k，但肯定不会对答案产生贡献所以没有影响。当右指针到终点，right - left + 1就是答案。
 需要注意的是，maxn 不是传统意义当前子串中最多重复元素个数，而是所有情况中的最大值，其是 >= 当前子串中最多重复元素个数，因为我们需要 right - left + 1 - 当前子串最多重复元素个数 是否 > k? 因为 maxn 本次没被更新，就和之前情况没有区别，所以用 right - left + 1 - maxn 是否 > k 来代替没有任何影响。
 
代码(官方) 
class Solution {
public:
    int characterReplacement(string s, int k) {
        vector num(26);
        int n = s.length();
        int maxn = 0;
        int left = 0, right = 0;
        while (right < n) {
            num[s[right] - 'A']++;
            maxn = max(maxn, num[s[right] - 'A']);
            if (right - left + 1 - maxn > k) {
                num[s[left] - 'A']--;
                left++;
            }
            right++;
        }
        return right - left;
    }
};