题解 | #牛牛的AC#

一.题目描述
NC535牛牛的AC
一年一度的春招就要到来了，牛牛为了备战春招，在家刷了很多道题，所以牛牛非常喜欢AC这两个字母。他现在有一个只包含A和C的字符串，你可以任意修改最多k个字符，让A变成C，或者C变成A。请问修改完之后，最长连续相同字符的长度是多少。
图片说明
二.算法(暴力)
对于题目的意思我们理解后就可以知道要求修改后最长连续相同字符的长度，我们可以用暴力遍历的方法，从头开始遍历字符串，每次遍历的开始的第一个点作为起点，然后往后面进行计数，如果起点为A，那么遇到C就变换，然后重新计数，同时维护最大值。下面是完整代码：

class Solution {
public:
    int Solve(int k, string s) {
        int ans=0;
        //把整个字符串遍历一遍，每一次开始的第一个点是起点
        for(int i=0;i<s.size();i++){ 
            int cnt=0; //记录修改了多少次字符
            int sum=1;  //对每一次记录的最大长度进行记录
            if(s[i]=='C'){ 
                //首字符为C
                for(int j=i+1;j<s.size();j++){
                    if(s[j]=='C'){
                         sum++;
                    } else if(cnt<k) {
                        //还可以修改那么把C改成A
                        cnt++,sum++;
                    } else{
                        break;
                    }
                }
                ans=max(ans,sum);
            }else{
                 //首字符为A
                for(int j=i+1;j<s.size();j++){
                    if(s[j]=='A') {
                        sum++;
                    } else if(cnt<k) {
                        //还可以修改那么把A改成C
                        cnt++,sum++;
                    } else {
                        break;
                    }
                }
                ans=max(ans,sum);
            }
        }
        return ans;
    }
};

时间复杂度： $O(n^{2})$ 进行了两次遍历，时间复杂度为O(n * n)
空间复杂度： $O(1)$ 没有使用额外的内存空间
优缺点：便于实现，但是时间复杂度高
三.算法(滑动窗口)
图片说明
算法二的复杂度很高我们需要对其进行进一步优化。首先我们基于贪心的想法，为了修改后我们可以获得最长的连续区间，我们可以修改连续区间之间的不同字符串从而获得最长的连续区间。对于区间问题我们又可以想到使用双指针模拟滑动窗口。我们可以遍历字符串s，每次遇到A则，cnta计数变量，遇到C则计数变量cntc，当这两个计数变量都没超过k的时候，可以相互之间任意变换，所以二者的数量相加即是当前最长的连续相同字母长度。当其中一个字符串个数超过，比如，那可以将前面的字母C（还没超过）全部变成A，因此依然还是当前最长的连续相同字母长度；当两个计数变量都超过了，相互之间无法变换了，我们可以利用窗口的思想，缩小左边的窗口(左边的指针加一)，左边放出哪个字母哪个字母的计数就减1，直到满足两个计数都不大于k，返回最后的最大值即可。下面是完整代码：

class Solution {
public:
    int Solve(int k, string s) {
        int cnta=0,cntc=0;
        //cnta,cntb分别记录字符串A和C的数目
        int ans=0;
        for(int l=0,r=0;r<s.size();r++){
            if(s[r]=='A'){
                cnta++;
            } else {
                cntc++;
            }
            //当两个字符的数量都大于k的时候 缩小窗口左指针右移
            while(cnta>k&&cntc>k){
                if(s[l++]=='A'){
                    cnta--;
                } else {
                    cntc--;
                }
            }
            //维护最大值
            ans=max(ans,cnta+cntc);
        }
        return ans;
    }
};

时间复杂度： $O(n)$ 只需要对字符串进行一次遍历
空间复杂度： $O(1)$ 不需要额外开辟空间
优缺点：时间复杂度低，但是不易实现