校招真题练习032 连续相同字符串(头条)

题目描述
有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。

输入描述:
第一行两个整数 n , m (1<=m<=n<=50000)，第二行为长度为n且只包含’a’和’b’的字符串s。

输出描述:
输出在操作次数不超过 m 的情况下，能够得到的最大连续全’a’子串或全’b’子串的长度。

 1 def change(string,target,m,n):
 2     left = 0
 3     changelist = []
 4     changecount = 0
 5     maxlen = 0
 6     i,j = 0,0
 7     while i < n:
 8         if string[i] == target:
 9             i += 1
10         else:
11             if changecount < m:
12                 changecount += 1
13                 changelist.append(i)
14                 i += 1
15             else:
16                 curleng = i - left
17                 if curleng > maxlen:
18                     maxlen = curleng
19                 left = changelist[j] + 1
20                 j += 1
21                 changecount -= 1
22     if len(changelist) > j:
23         curleng = n - left
24         if curleng > maxlen:
25             maxlen = curleng
26     return maxlen
27 
28 def main():
29     ary1 = list(map(int,input().split()))
30     n,m = ary1[0],ary1[1]
31     string = input().strip()
32     c1 = change(string,'b',m,n)
33     c2 = change(string,'a',m,n)
34     if c1 >= c2:
35         print(c1)
36     else:
37         print(c2)
38 
39 if __name__ == '__main__':
40     main()

算法思路：双指针，滑动窗口。

依据题意，需要尝试两种转换方式：1.将'a'转换为'b'，2.将'b'转换为'a'。

对于每一种转换，滑动窗口内部是完成m次转换的区域。当完成m次转换之后，计算当前区域的长度，并进行窗口的滑动。