2811:好看的字符串

时间限制:2 S   /  内存限制:65536 KB
AC:143   /  Submit:311
问题描述

罗少很喜欢字符串,他认为一个字符串相同的字符越少,这个字符串就越好看,在他心里有这样一个定义:

如果某个字符在这个字符串中只出现了一次,那么这个字符串的好看值就加一,如果某个字符在这个字符串中出现了 n(n>1) 次,那么这个字符串的好看值就要减去 (n - 1)。

例如字符串:abacccde,初始时这个字符串的好看值为 m = 0

a 在这个字符串中出现了 2 次,所以 m -= (2 - 1)

b 在这个字符串中出现了 1 次,所以 m += 1

c 在这个字符串中出现了 3 次,所以 m -= (3 - 1)

d 在这个字符串中出现了 1 次,所以 m += 1

e 在这个字符串中出现了 1 次,所以 m += 1

最后,这个字符串的好看值 m = -1 + 1 - 2 + 1 + 1 = 0

罗少发现,字符串越长,字符相同的数量就越多,好看值也会越低,因此他想要在一个字符串中截取出他认为最好看的一段(必须是连续的),由于这样的字符串可能不止一段,所以你只需要回答罗少最后截取的那段字符串的好看值是多少就可以了。

输入描述

第一行是一个正整数 T 代表测试案例的数量。(1 <= T <= 100)

每组案例先是一个正整数 n 代表字符串的长度。(1 <= n <= 300)

然后是 n 个小写字符

输出描述

针对每组案例,输出最好看的那段字符串的好看值,然后换行。

样例输入复制样例

2

6

abcaac

7

abccdef

样例输出

3

4

提示说明

第一组样例中最好看的一段是 “abc”,好看值为 3。

第二组样例中最好看的一段是 “abccdef”,好看值为 5 - 1 = 4。

相关

19-20(2)第4次线上赛

题单#5(前缀和、差分数组)


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1