一年一度的春招就要到来了,牛牛为了备战春招,在家刷了很多道题,所以牛牛非常喜欢AC这两个字母。他现在有一个只包含A和C的字符串,你可以任意修改最多k个字符,让A变成C,或者C变成A。请问修改完之后,最长连续相同字符的长度是多少。
1,"AAAC"
4
样例一:将最后一位C改成A即可。
字符串长度<=10^6,且只包含'A'和'C',k<=10^6。
Python3滑动窗口,区间内a、c数量不都大于k时计算长度并移动右端点,反之移动左端点
class Solution: def Solve(self , k , s ): if s == '': return 0 res, left, right, l = 1, 0, 0, len(s) a_num = 0 if s[0] == 'C' else 1 c_num = 0 if s[0] == 'A' else 1 while True: if a_num > k and c_num > k: if s[left] == 'A': a_num -= 1 else: c_num -= 1 left += 1 else: res = max(res, right-left+1) right += 1 if right == l: break else: if s[right] == 'A': a_num += 1 else: c_num += 1 return res
class Solution { public: /** * * @param k int整型 * @param s string字符串 * @return int整型 */ int Solve(int k, string s) { int a=0, c=0, Max=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--; } Max = max(Max, a+c); } return Max; } };
public int Solve(int k, String s) { char[] chs = s.toCharArray(); int start = 0, end = 0, n = s.length(), max = 0, a = 0, c = 0; while (end < n) { if (chs[end++] == 'A') a++; else c++; while (a > k && c > k) { if (chs[start++] == 'A') a--; else c--; } max = Math.max(a + c, max); } return max; }