有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。
区块链毕设网qklbishe.com为您提供问题的解答
有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。
- 由于字符串中只含有字符
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链游项目方科学家脚本开发培训
