题解 | #牛牛的AC#

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

方法一：暴力解法

枚举每一个字符作为起始点，记录下起始字符，从起始字符后的第一个字符开始遍历，用cnt记录本次找到的最长字符长度
如果遇到与起始字符相同的字符，则cnt增加，否则
1. $k>0$ ,修改字符到相同，记录修改次数 $countK++$
2. $k=0$ 或者修改次数已经到 $k$ 了,跳出本轮循环
结束一轮循环后，更新最大值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param k int整型 
     * @param s string字符串 
     * @return int整型
     */
    public int Solve (int k, String s) {
        // write code here
        int max=0;
        //枚举每一个字符作为起始点
        for(int start=0;start<s.length();start++){
            //记录起始字符
            char startChar=s.charAt(start);
            //cnt记录本次最长字符串的长度，countK记录本次修改的次数
            int cnt=1,countK=0;
            //从起始字符后的第一个字符开始比较
            for(int i=start+1;i<s.length();i++)
            {
                if(s.charAt(i)==startChar)cnt++;//遇到与起始字符相同的长度增加
                else if(countK<k)//否则将它从A(C)变为C(A)，修改次数要小于k
                {
                    countK++;
                    cnt++;
                }
                else break;//当修改次数增加到等于k或者k本身为0时跳出本次循环
            }
            max=Math.max(max,cnt);//记录最大值
        }
        return max;
    }
}

复杂度：
时间复杂度：外层循环遍历字符串一次，内层循环的遍历次数不超过字符串的长度n，因此最坏时间复杂度不超过 $图片说明$
空间复杂度：只是额外定义了几个临时变量，使用了常数个额外空间，空间复杂度为 $O(1)$
方法二：滑动窗口
暴力解法枚举每个字符作为起点，存在许多重复运算，可以采用滑动窗口解决本题
设置左指针和右指针都指向字符串起始点，字符串包含A和C，让右指针右移，不断扩大窗口，遇到A则 $a++$ (A的个数),遇到C则 $c++$ (C的个数),只要a和c有一方不超过k，窗口就可以不断扩大，不超过k的那方就可以转换为另一方,此时最长字符串长度就为 $a+c$ ,当两方都超过k时，左指针需要右移，缩小左边窗口，如果缩小的是A， $a--$ ，否则 $c--$ ，在窗口扩大与缩小后记录最大值，直到右指针到达末尾，返回这个过程中找到的最长字符串长度

图片说明

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param k int整型 
     * @param s string字符串 
     * @return int整型
     */
    public int Solve (int k, String s) {
        // write code here
        int l=0,r=0,max=0,a=0,c=0;
        //左指针不动，右指针向右移动
        while(r<s.length()){
            //记录A的个数
            while(r<s.length()&&s.charAt(r)=='A'){r++;a++;}
            //记录C的个数
            while(r<s.length()&&s.charAt(r)=='C'){r++;c++;}
            //当A的个数大于k并且C的个数也大于k时，左指针移动缩小窗口，保持a或者c有一个不超过k
            while(a>k&&c>k){
                //如果缩小的是A，则A的个数减少，否则C的个数减少
                if(s.charAt(l++)=='A')a--;
                else c--;
            }
            //维护最大值
            max=Math.max(max,a+c);
        }
        return max;
    }
}

复杂度：
时间复杂度：遍历字符串一次， $O(n)$
空间复杂度：只是额外定义了几个临时变量，使用了常数个额外空间，空间复杂度为 $O(1)$