CF2254B Evanescent

设 $f(s)$ 是字符串 $s$ 的压缩版本，通过将每个由相同字符组成的极大连续子段替换为该字符的单个副本得到。例如，$f($"aabbcc"$) = $ "abc"。 记 $|s|$ 表示字符串 $s$ 的长度，则 $|f(s)|$ 表示压缩后字符串的长度。例如： - $|f($"aabbcc"$)| = $ $|$"abc"$|$ $= 3$ - 若字符串为空，长度为 $0$。 Yousef 给你一个长度为 $n$ 仅包含小写拉丁字母的字符串 $s$。你需要删除恰好一个字符 $s_i$（$2 \le i \le n-1$），形成一个新字符串 $s'$，然后求 $|f(s')|$ 的最小可能值。 注意，你不能删除 $s_1$ 或 $s_n$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行为一个整数 $n$（$3 \le n \le 2 \cdot 10^5$），表示字符串的长度。 第二行为一个长度为 $n$ 且只含小写拉丁字母的字符串 $s$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行一个整数，表示删除一个字符后，所得压缩字符串的最小长度。

在第一个测试用例中，唯一可以删除的是字符 $s_2 = $ 'b'，得到 $s' = $ "ab"，此时 $|f(s')| = 2$。因此，最小可达长度为 $2$。 在第四个测试用例中，我们可以删除字符 $s_2 = $ 'b'。所得字符串为 $s' = $ "aaa"，此时 $f(s') = $ "a"，故 $|f(s')| = 1$。 在第六个测试用例中，无论删除哪个合法字符，压缩后都得到 $f(s') = $ "e"，$|f(s')| = 1$。 在第八个测试用例中，我们可以删除字符 $s_4 = $ 'c'，得到 $s' = $ "abaaba"，$f(s') = $ "ababa"$，$|f(s')| = 5$。 由 ChatGPT 5 翻译