第一行两个整数 n , m (1<=m<=n<=50000),第二行为长度为n且只包含’a’和’b’的字符串s。
输出在操作次数不超过 m 的情况下,能够得到的 最大连续 全’a’子串或全’b’子串的长度。
8 1 aabaabaa
5
把第一个 'b' 或者第二个 'b' 置成 'a',可得到长度为 5 的全 'a' 子串。
'''不会写,乱写的''' 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))
a
和 b
,因此分别考虑相同字符为 a
和 b
的最长子串。 a
为例,操作次数取决于子串中 b
的数目,可以将其存储在前缀和数组 pre
中。考虑当前遍历的位置 i
,问题转变为在 pre
中向前找到满足 pre[i] - pre[j] <= m
的最小下标 j
。 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")))