题目描述

我们定义字符串 $x$ 的函数 $f(x)$ 为该字符串中不同字符的数量。例如，$f(\texttt{abc}) = 3$，$f(\texttt{bbbbb}) = 1$，$f(\texttt{babacaba}) = 3$。

给定一个字符串 $s$，请将其拆分为两个非空字符串 $a$ 和 $b$，使得 $f(a) + f(b)$ 的值最大。换句话说，找到 $f(a) + f(b)$ 的最大可能值，其中 $a + b = s$（即字符串 $a$ 与字符串 $b$ 拼接后等于字符串 $s$）。

输入格式

输入包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2\cdot10^5$），表示字符串 $s$ 的长度。

第二行包含一个仅由小写英文字母组成的字符串 $s$。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

输出格式

对于每个测试用例，输出一个整数，表示满足 $a + b = s$ 的情况下 $f(a) + f(b)$ 的最大可能值。

样例

5
2
aa
7
abcabcd
5
aaaaa
10
paiumoment
4
aazz

2
7
2
10
3

样例说明

对于第一个测试用例，只有一种有效的拆分方式，即将 $\texttt{aa}$ 拆分为两个非空字符串 $\texttt{a}$ 和 $\texttt{a}$，此时 $f(\texttt{a}) + f(\texttt{a}) = 1 + 1 = 2$。

对于第二个测试用例，将 $\texttt{abcabcd}$ 拆分为 $\texttt{abc}$ 和 $\texttt{abcd}$ 可以得到答案 $f(\texttt{abc}) + f(\texttt{abcd}) = 3 + 4 = 7$，这是最大可能值。

对于第三个测试用例，无论如何拆分字符串，答案始终为 $2$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1791D，英文题名 Distinct Split。