幸运N串-研发

[编程题]幸运N串-研发

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

小A很喜欢字母N，他认为连续的N串是他的幸运串。有一天小A看到了一个全部由大写字母组成的字符串，他被允许改变最多2个大写字母（也允许不改变或者只改变1个大写字母），使得字符串中所包含的最长的连续的N串的长度最长。你能帮助他吗？

输入描述:

输入的第一行是一个正整数T（0 < T <= 20），表示有T组测试数据。对于每一个测试数据包含一行大写字符串S（0 < |S| <= 50000，|S|表示字符串长度）。

数据范围：

20%的数据中，字符串长度不超过100；

70%的数据中，字符串长度不超过1000；

100%的数据中，字符串长度不超过50000。

输出描述:

对于每一组测试样例，输出一个整数，表示操作后包含的最长的连续N串的长度。

示例1

输入

3
NNTN
NNNNGGNNNN
NGNNNNGNNNNNNNNSNNNN

输出

4
10
18

算法知识视频讲解

Python

牛客961885550号

不用pop的方法
T = int(input())
for i in range(T):
    s = list(input())
    su = 0
    m = []
    for i in range(len(s)):
        if s[i] == 'N':
            su += 1
        else:
            m.append(i)
    if len(m) <= 2:
        print(len(s))
    else:
        length=[]
        length.append(m[2]+1)
        for k in range(1,len(m)-2):
                length.append((m[k + 2] - m[k-1]))
        length.append(len(s)-m[len(m)-3])
        print(max(length)-1)

编辑于 2020-09-04 21:03:00 回复(0)