codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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