连续相同字符串(编程题2)

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

 

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

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

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