题解 | #牛牛的AC#

题目描述
一年一度的春招就要到来了，牛牛为了备战春招，在家刷了很多道题，所以牛牛非常喜欢AC这两个字母。他现在有一个只包含A和C的字符串，你可以任意修改最多k个字符，让A变成C，或者C变成A。请问修改完之后，最长连续相同字符的长度是多少。

方法一：暴力求解

求解思路
对于本题目的求解，我们可以用暴力遍历的方法，遍历字符串，每次遍历的点作为起点，然后往后面进行计数，如果起点为A，那么遇到C就变换，然后重新计数，同时维护最大值。按照上述思路，即可得到本问题的答案。

图片说明

解题代码

class Solution {
public:
    int Solve(int k, string s) {
        int myres = 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;
                }
                myres = max(myres, 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;
                }
                myres = max(myres, temp); // 对结果进行更新
            }
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：没有使用额外的内存地址空间，因此空间复杂度为 $O(1)$

方法二：贪心思想求解

求解思路
对于本题我们也可以使用贪心的思想进行求解，遍历字符串，每次遇到A则计数a+1,遇到C则c+1，当这两个计数变量都没超过k时可以任意变换一个到另一个。当超过k时，比如a>k,则字母C全部变成A，并且同时维护最大值。按照上述思想，即可得到本问题的答案。

图片说明

解题代码

class Solution {
public:
    int Solve(int k, string s) {
        int counta = 0; // 字母A的计数变量
        int countc = 0; // 字母C的计数变量
        int myres = 0; // 存储结果
        for(int l = 0, r = 0; r < s.length(); r++)
        {   //窗口右侧增长
            if(s[r] == 'A')
                counta++;
            else
                countc++;
            while(counta > k && countc > k)
            {   //窗口左侧收缩
                if(s[l++] == 'A')
                    counta--;
                else
                    countc--;
            }
            myres = max(myres, counta + countc); // 更新结果
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：没有使用额外的内存地址空间，因此空间复杂度为 $O(1)$