编程题2

'''不会写，乱写的'''
nums=input().split()
s=input()
n=int(nums[0])
m=int(nums[1])
def check(s,k,a):
    n=len(s)
    dp=[0]*(n+1)
    c=0
    for i in range(n):
        if s[i]==a:
            c+=1
            dp[i+1]=c 
    #先判断每个位置之前一共有多少个‘a’
    l=0
    r=0
    max_l=0
    while r<n+1:
        if  dp[r]-dp[l]<=k and r<=n:
            max_l=max(max_l,r-l)
            r+=1
        else:
            l+=1
    max_l=max(max_l,r-l-1)
    return max_l
ss=check(s,m,"a")
xx=check(s,m, "b")
print (max(ss,xx))

1. 由于字符串中只含有字符 a 和 b ，因此分别考虑相同字符为 a 和 b 的最长子串。
2. 以字符 a 为例，操作次数取决于子串中 b 的数目，可以将其存储在前缀和数组 pre 中。考虑当前遍历的位置 i ，问题转变为在 pre 中向前找到满足 pre[i] - pre[j] <= m 的最小下标 j 。
3. 子串的长度越长，包含 b 的数目只有可能增加或保持不变，而不会减少，存在单调性，可以采用搜索左侧边界的二分查找。

import bisect
from typing import List


def solve(s: List[str], m: int, ch: str) -> int:
    pre, count = [0], 0
    result = 0
    for i, v in enumerate(s):
        count = count + 1 if v == ch else count
        pre.append(count)
        idx = bisect.bisect_left(pre, count - m)
        result = max(result, i - idx + 1)

    return result


_, m = list(map(int, input().split(" ")))
s = input()
print(max(solve(s, m, "a"), solve(s, m, "b")))