首页 > 试题广场 >

编程题2

[编程题]编程题2

热度指数：395 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

第一行两个整数 n , m (1<=m<=n<=50000)，第二行为长度为n且只包含’a’和’b’的字符串s。

输出描述:

输出在操作次数不超过 m 的情况下，能够得到的 最大连续 全’a’子串或全’b’子串的长度。

示例1

输入

8 1
aabaabaa

输出

说明

把第一个 'b' 或者第二个 'b' 置成 'a'，可得到长度为 5 的全 'a' 子串。

算法知识视频讲解

Python

牛客341441072号

res = 0
indexa,indexb=[],[]
for i in range(n):
    if  string[i]=='a':
        indexa.append(i)
    else:
        indexb.append(i)
for i in range(2):
    if i==0:
        arrs = indexa
    else:
        arrs = indexb
    if len(arrs)<=m:
        res = n
        break
    for j in range(len(arrs)-m-1):
        tmp = arrs[j+m+1]-arrs[j]-1
        res = max(res,tmp)
    res = max(res,arrs[m])
    res = max(res,n-1-arrs[-(m+1)])
print(res)

两种字符的转换可以直接分两种情况讨论，a->b或b->a。先保存下a与b的下标，随后分三种情况讨论：中间段；0到arrs[m]；arrs[-(m+1)]到n-1。取三种情况的最大值就是最终结果。

发表于 2020-05-02 20:57:03 回复(0)