A16776 | $String Rotation Game$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

定义一个字符串中的“块”为一个由相同字符类型组成的连续子串，并且该子串无法向左或向右扩展。例如，在字符串 aabcccdaa 中，有五个块： - aa（第 $1$ 到第 $2$ 个字符） - b（第 $3$ 个字符） - ccc（第 $4$ 到第 $6$ 个字符） - d（第 $7$ 个字符） - aa（第 $8$ 到第 $9$ 个字符） 你在玩一个游戏，给定一个长度为 $n$ 的字符串 $s$。你可以随意对字符串进行循环旋转*。你的得分是最终字符串中块的数量。请找出可能的最大得分。 *正式定义：选择一个索引 $1 \le i \le n$，将字符串 $s_1s_2 \dots s_n$ 改成 $s_{i+1}s_{i+2} \dots s_ns_1s_2 \dots s_i$。例如，字符串 abcde 可以通过选择 $i=3$ 旋转为 deabc。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t(1 \le t \le 500)$。 每个测试用例的第一行包含一个整数 $n(1 \le n \le 100)$。 每个测试用例的第二行包含字符串 $s$，长度为 $n$。 字符串 $s$ 仅由小写拉丁字母组成。

对于每个测试用例，输出一个整数，表示可能的最大得分。

输入 #1

4
4
abcd
4
abbc
4
abba
6
abbccc

输出 #1

C++ 编辑器

输入

输出