首页 > 试题广场 >

编程题2

[编程题]编程题2

热度指数：12868 时间限制：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

给我个端茶倒水的机会

参考猪大哥的代码写的python，滑动窗口版本

def find(n,m,lis):
    max1=0
    l=0
    r=0
    an=0
    bn=0
    while r<n:
        if lis[r]=="a":
            an +=1
        else:
            bn +=1
        if an<=m or bn<=m:
            r +=1
        else:
            if (r-l)>max1:
                max1=r-l
            if lis[l]=='a':
                l +=1
                an -=1
            else:
                l +=1
                bn -=1
            r +=1
    return max1

n,m=map(int,input().split())
lis=list(input())
b=find(n, m, lis)
print(b)

发表于 2020-08-19 21:16:18 回复(0)

Python

牛客155955564号

def solution(n, m, s, c):
    b = []
    for i in range(n):
        if s[i] == c:
            b.append(i)
    if m >= len(b):
        return n
    res = max(b[m], n - b[-1-m] - 1)
    for j in range(m, len(b)):
        res = max(res, b[j] - b[max(0, j-m-1)] - 1)
    return res
if __name__ == '__main__':
    n, m = map(int, input().split())
    s = str(input())
    print(max(solution(n, m, s, 'a'), solution(n, m, s, 'b')))

发表于 2020-08-12 09:32:08 回复(1)

Python

cesc_wang

while True:
    try:
        line = list(map(int, input().split()))
        n, m = line[0], line[1]
        s = input()
        i, j = 0, 0
        countA, countB = 0, 0
        if s[0] == "a":
            countA += 1
        else:
            countB += 1
        res = 0
        while i <= j and j < n - 1:
            if countA <= m or countB <= m:
                res = max(res, j-i+1)
                j += 1
                if s[j] == "a":
                    countA += 1
                else:
                    countB += 1
            else:
                i += 1
                if s[i-1] == "a":
                    countA -= 1
                else:
                    countB -= 1
        print(res)
    except:
        break

发表于 2019-03-14 15:33:34 回复(0)

Python

兰偷荀令香

n, m = map(int, input().strip().split())
str_n = list(input().strip())

def find_best_sub_string(char_digit): # 变成char_digit后的最长子串
lst = [-1]
for i in range(len(str_n)):
if str_n[i] != char_digit:
lst.append(i)
lst.append(len(str_n))
if len(lst) - 2 <= m:
return len(str_n)
else:
max_length = 0
for j in range(1, len(lst) - m):
if max_length < (lst[j + m] - lst[j - 1] - 1):
max_length = lst[j + m] - lst[j - 1] - 1
return max_length

print(max(find_best_sub_string('a'), find_best_sub_string('b')))

发表于 2019-02-20 10:45:44 回复(0)

Python

嘿哈嘿

## 19:45 -- 20:27
n, m = [int(x) for x in input().split()]
s = input()
max_a = 0
max_b = 0
a_index = []
b_index = []
for i in range(n):
    if s[i] == 'a':
        a_index.append(i)
    else :
        b_index.append(i)
if len(a_index) <= m or len(b_index) <= m :
    print(n)
else :
    for i in range(len(a_index) - m):
        if i == 0:
            temp = a_index[m]
            if temp > max_b :
                max_b = temp
        elif i == len(a_index) - m :
            temp = n - a_index[i]
            if temp > max_b :
                max_b = temp
                print(i)
        else :
            temp = a_index[m+i] - a_index[i-1] - 1
            if temp > max_b :
                max_b = temp
    
    for i in range(len(b_index) - m):
        if i == 0:
            temp = b_index[m]
            if temp > max_a :
                max_a = temp
        elif i == len(b_index) - m :
            temp = n - b_index[i]
            if temp > max_a :
                max_a = temp
        else :
            temp = b_index[m+i] - b_index[i-1] - 1
            if temp > max_a :
                max_a = temp
    print(max(max_a, max_b))

发表于 2019-02-17 20:27:55 回复(1)