题解 | #牛牛的AC#

思路：

题目的主要信息：

• 字符串中只有字母AC
• 可选择任意k次变换将某个位置的字母变成另一个字母，求修改后的最长连续相同字母长度

方法一：暴力法
具体做法：
遍历字符串，每次遍历的点作为起点，如果起点为A，则第二次遍历后续遇到A直接计数，遇到C变换次数减1再计数，如果超过变换次数则与记录的最大值比较，维护最大值；如果起点为C，同理。

class Solution {
public:
    int Solve(int k, string s) {
        int res = 0;
        for(int i = 0; i < s.length(); i++){ //每个字符都可以作为起点
            int count = 0; //记录修改了多少次
            int temp = 1;  //记录本次的最大长度
            if(s[i] == 'A'){ //首字符为A
                for(int j = i + 1; j < s.length(); j++){
                    if(s[j] == 'A') 
                        temp++;
                    else if(count < k){ //出现C，转变成A
                        count++;
                        temp++;
                    }
                    else
                        break;
                }
                res = max(res, temp);
            }else{//首字符为C
                for(int j = i + 1; j < s.length(); j++){
                    if(s[j] == 'C')
                        temp++;
                    else if(count < k){//出现A，转变成C
                        count++;
                        temp++;
                    }
                    else
                        break;
                }
                res = max(res, temp);
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，两层遍历，每层都是
• 空间复杂度：，无额外空间使用，都是常数量级

方法二：贪心+滑动窗口
具体做法：
我们可以用贪心思想加上滑动窗口来解决。
遍历字符串s，每次遇到A则，计数变量，遇到C则计数变量，当这两个计数变量都没超过的时候，可以任意变换一个到另一个，所以二者相加即是当前最长的连续相同字母长度；当其中一个字符串个数超过，比如，那可以将前面的字母C（还没超过）全部变成A，因此依然还是当前最长的连续相同字母长度；当两个计数变量都超过了，这是肯定无法变换了，我们可以利用窗口的思想，缩小左边的窗口，左边放出哪个字母哪个字母的计数就减1，直到满足两个计数都不大于。
如下图所示，每次记得维护最大值即可。

class Solution {
public:
    int Solve(int k, string s) {
        int a = 0;
        int c = 0;
        int res = 0;
        for(int l = 0, r = 0; r < s.length(); r++){ //窗口右侧增长
            if(s[r] == 'A')
                a++;
            else
                c++;
            while(a > k && c > k){ //窗口左侧收缩
                if(s[l++] == 'A')
                    a--;
                else
                    c--;
            }
            res = max(res, a + c);
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，只有一次遍历
• 空间复杂度：，常数级临时变量，无额外使用空间