CF1791D Distinct Split

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 $ .

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 $ .