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

区块链毕设网qklbishe.com为您提供问题的解答

由于字符串中只含有字符 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")))

12:00

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

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。

区块链NFT链游项目方科学家脚本开发培训