问题2287--不断减损的时间

2287: 不断减损的时间

[命题人 : ]
时间限制 : 1 sec  内存限制 : 128 MB

提交
解决: 10提交量: 62统计

题目描述

风情找到了一个包含 n 个小写拉丁字母的字符串 s ，并且他希望将其尽可能地缩短。为了做到这一点，他可以任意次数地删除 s 中任意数量的相邻且不同字符对。例如，如果s=racoon，那么通过删除一个相邻且不同字符对，他可以得到字符串 coon、roon、raon 和 raco，但他不能得到 racn（因为删除的字母相同）或 rcon（因为删除的字母不相邻）。风情可以通过任意次删除来达到的最小长度是多少？

输入

输入的第一行包含一个整数 T(1<=T<=100)表示测试用例的数量。

每个测试用例的第一行包含一个整数 n(1<=n<=105)，表示字符串 s 的长度。

每个测试用例的第二行包含一个由 n 个小写拉丁字母组成的字符串 s。

保证所有测试用例中 n 的总和不超过 2*105

输出

对于每个测试用例，输出一个数字，表示在删除相邻且不同字符对后，字符串 s 的最小长度。

样例输入 Copy 

3
4
aabc
5
abaca
10
avbvvcvvvd

样例输出 Copy 

0
1
2

提示

在示例的第一个测试用例中，你需要按照以下步骤进行操作：aabc → ac → ""。请注意，以不同的删除顺序，字符串将不会变为空。

来源/分类

计算机学院2023级程序设计提升班选拔赛（1） 
提交