codeforces-scrape

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

1660C.md (2042B)


      1 Source: https://codeforces.com/problemset/problem/1660/C
      2 
      3 C. Get an Even String
      4 
      5 time limit per test
      6 
      7 1 second
      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 A string $a=a_1a_2\dots a_n$ is called even if it consists of a concatenation (joining) of strings of length $2$ consisting of the same characters. In other words, a string $a$ is even if two conditions are satisfied at the same time:
     22 
     23 * its length $n$ is even;
     24 * for all odd $i$ ($1 \le i \le n - 1$), $a_i = a_{i+1}$ is satisfied.
     25 
     26 For example, the following strings are even: "" (empty string), "tt", "aabb", "oooo", and "ttrrrroouuuuuuuukk". The following strings are not even: "aaa", "abab" and "abba".
     27 
     28 Given a string $s$ consisting of lowercase Latin letters. Find the minimum number of characters to remove from the string $s$ to make it even. The deleted characters do not have to be consecutive.
     29 
     30 Input
     31 
     32 The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.
     33 
     34 The descriptions of the test cases follow.
     35 
     36 Each test case consists of one string $s$ ($1 \le |s| \le 2 \cdot 10^5$), where $|s|$ — the length of the string $s$. The string consists of lowercase Latin letters.
     37 
     38 It is guaranteed that the sum of $|s|$ on all test cases does not exceed $2 \cdot 10^5$.
     39 
     40 Output
     41 
     42 For each test case, print a single number — the minimum number of characters that must be removed to make $s$ even.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 6
     50 
     51 aabbdabdccc
     52 
     53 zyx
     54 
     55 aaababbb
     56 
     57 aabbcc
     58 
     59 oaoaaaoo
     60 
     61 bmefbmuyw
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 3
     68 3
     69 2
     70 0
     71 2
     72 7
     73 ```
     74 
     75 Note
     76 
     77 In the first test case you can remove the characters with indices $6$, $7$, and $9$ to get an even string "aabbddcc".
     78 
     79 In the second test case, each character occurs exactly once, so in order to get an even string, you must remove all characters from the string.
     80 
     81 In the third test case, you can get an even string "aaaabb" by removing, for example, $4$-th and $6$-th characters, or a string "aabbbb" by removing the $5$-th character and any of the first three.