codeforces-scrape

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

1907C.md (1789B)


      1 Source: https://codeforces.com/problemset/problem/1907/C
      2 
      3 C. Removal of Unattractive Pairs
      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 Vlad found a string $s$ consisting of $n$ lowercase Latin letters, and he wants to make it as short as possible.
     22 
     23 To do this, he can remove any pair of adjacent characters from $s$ any number of times, provided they are different. For example, if $s$=racoon, then by removing one pair of characters he can obtain the strings coon, roon, raon, and raco, but he cannot obtain racn (because the removed letters were the same) or rcon (because the removed letters were not adjacent).
     24 
     25 What is the minimum length Vlad can achieve by applying any number of deletions?
     26 
     27 Input
     28 
     29 The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Descriptions of the test cases follow.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.
     32 
     33 The second line of each test case contains the string $s$ consisting of $n$ lowercase Latin letters.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, output a single number—the minimum length of the string $s$, after removing pairs of adjacent characters with different values.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 10
     47 
     48 4
     49 
     50 aabc
     51 
     52 5
     53 
     54 abaca
     55 
     56 10
     57 
     58 avbvvcvvvd
     59 
     60 7
     61 
     62 abcdefg
     63 
     64 5
     65 
     66 dabbb
     67 
     68 8
     69 
     70 aacebeaa
     71 
     72 7
     73 
     74 bbbbacc
     75 
     76 6
     77 
     78 dacfcc
     79 
     80 6
     81 
     82 fdfcdc
     83 
     84 9
     85 
     86 dbdcfbbdc
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 0
     93 1
     94 2
     95 1
     96 1
     97 0
     98 1
     99 0
    100 0
    101 1
    102 ```
    103 
    104 Note
    105 
    106 In the first test case of the example, you need to act as follows: "aabc" $\rightarrow$ "ac" $\rightarrow$ "". Note that with a different order of deletions, the string will not become empty.