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.