Distinct Split

题意翻译

定义函数 $f(s)$ 表示字符串 $s$ 中有多少个不同的字符，例如 $f(\texttt{abc})=3, f(\texttt{abababbb})=2$。 现给定一个字符串 $s$，求 $\max\{f(a)+f(b)\}$，$a$ 和 $b$ 拼接在一起为 $s$。

题目描述

Let's denote the $ f(x) $ function for a string $ x $ as the number of distinct characters that the string contains. For example $ f(\texttt{abc}) = 3 $ , $ f(\texttt{bbbbb}) = 1 $ , and $ f(\texttt{babacaba}) = 3 $ . Given a string $ s $ , split it into two non-empty strings $ a $ and $ b $ such that $ f(a) + f(b) $ is the maximum possible. In other words, find the maximum possible value of $ f(a) + f(b) $ such that $ a + b = s $ (the concatenation of string $ a $ and string $ b $ is equal to string $ s $ ).

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 2 \leq n \leq 2\cdot10^5 $ ) — the length of the string $ s $ . The second line contains the string $ s $ , consisting of lowercase English letters. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

输出格式

For each test case, output a single integer — the maximum possible value of $ f(a) + f(b) $ such that $ a + b = s $ .

输入输出样例

输入样例 #1

5
2
aa
7
abcabcd
5
aaaaa
10
paiumoment
4
aazz

输出样例 #1

2
7
2
10
3

说明

For the first test case, there is only one valid way to split $ \texttt{aa} $ into two non-empty strings $ \texttt{a} $ and $ \texttt{a} $ , and $ f(\texttt{a}) + f(\texttt{a}) = 1 + 1 = 2 $ . For the second test case, by splitting $ \texttt{abcabcd} $ into $ \texttt{abc} $ and $ \texttt{abcd} $ we can get the answer of $ f(\texttt{abc}) + f(\texttt{abcd}) = 3 + 4 = 7 $ which is maximum possible. For the third test case, it doesn't matter how we split the string, the answer will always be $ 2 $ .

**题目大意**

定义一个函数 $ f(s) $，它表示字符串 $ s $ 中不同字符的数量。例如，$ f(\texttt{abc})=3 $，$ f(\texttt{abababbb})=2 $。给定一个字符串 $ s $，要求将其拆分成两个非空字符串 $ a $ 和 $ b $，使得 $ f(a) + f(b) $ 的值最大。换句话说，就是找到使得 $ f(a) + f(b) $ 最大的 $ a $ 和 $ b $，使得 $ a + b = s $。

**输入输出数据格式**

**输入格式：**
- 输入包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $）——测试用例的数量。
- 每个测试用例的第一行包含一个整数 $ n $（$ 2 \leq n \leq 2 \times 10^5 $）——字符串 $ s $ 的长度。
- 第二行包含由小写英文字母组成的字符串 $ s $。
- 保证所有测试用例中 $ n $ 的总和不超过 $ 2 \times 10^5 $。

**输出格式：**
- 对于每个测试用例，输出一个整数——使得 $ a + b = s $ 的 $ f(a) + f(b) $ 的最大可能值。

**输入输出样例**

**输入样例 #1：**
```
5
2
aa
7
abcabcd
5
aaaaa
10
paiumoment
4
aazz
```

**输出样例 #1：**
```
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 $。**题目大意** 定义一个函数 $ f(s) $，它表示字符串 $ s $ 中不同字符的数量。例如，$ f(\texttt{abc})=3 $，$ f(\texttt{abababbb})=2 $。给定一个字符串 $ s $，要求将其拆分成两个非空字符串 $ a $ 和 $ b $，使得 $ f(a) + f(b) $ 的值最大。换句话说，就是找到使得 $ f(a) + f(b) $ 最大的 $ a $ 和 $ b $，使得 $ a + b = s $。 **输入输出数据格式** **输入格式：** - 输入包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $）——测试用例的数量。 - 每个测试用例的第一行包含一个整数 $ n $（$ 2 \leq n \leq 2 \times 10^5 $）——字符串 $ s $ 的长度。 - 第二行包含由小写英文字母组成的字符串 $ s $。 - 保证所有测试用例中 $ n $ 的总和不超过 $ 2 \times 10^5 $。 **输出格式：** - 对于每个测试用例，输出一个整数——使得 $ a + b = s $ 的 $ f(a) + f(b) $ 的最大可能值。 **输入输出样例** **输入样例 #1：** ``` 5 2 aa 7 abcabcd 5 aaaaa 10 paiumoment 4 aazz ``` **输出样例 #1：** ``` 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 $。