1791D.md (1883B)
1 Source: https://codeforces.com/problemset/problem/1791/D 2 3 D. Distinct Split 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 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$). 24 25 Input 26 27 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. 28 29 The first line of each test case contains an integer $n$ ($2 \leq n \leq 2\cdot10^5$) — the length of the string $s$. 30 31 The second line contains the string $s$, consisting of lowercase English letters. 32 33 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$. 34 35 Output 36 37 For each test case, output a single integer — the maximum possible value of $f(a) + f(b)$ such that $a + b = s$. 38 39 Example 40 41 Input 42 43 ``` 44 5 45 46 2 47 48 aa 49 50 7 51 52 abcabcd 53 54 5 55 56 aaaaa 57 58 10 59 60 paiumoment 61 62 4 63 64 aazz 65 ``` 66 67 Output 68 69 ``` 70 2 71 7 72 2 73 10 74 3 75 ``` 76 77 Note 78 79 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$. 80 81 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. 82 83 For the third test case, it doesn't matter how we split the string, the answer will always be $2$.