2145C.md (2671B)
1 Source: https://codeforces.com/problemset/problem/2145/C 2 3 C. Monocarp's String 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 Monocarp has a string $s$ of length $n$, consisting of the letters 'a' and 'b'. He wants to remove some (possibly zero) number of consecutive letters from his string in such a way that the number of letters 'a' and 'b' in the resulting string becomes equal. Monocarp can start removing letters from any position in the string $s$. 22 23 Monocarp really likes his string $s$, so he wants to remove as few consecutive letters from it as possible. 24 25 Your task is to determine the minimum number of consecutive letters from the string $s$ that need to be removed so that the number of letters 'a' and 'b' in the resulting string becomes equal. If it is necessary to remove all letters from the string $s$ (i.e., make it empty), report this. 26 27 Input 28 29 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 Each test case consists of two lines: 32 33 * the first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of characters in the string $s$; 34 * the second line contains the string $s$ of length $n$, consisting of the letters 'a' and/or 'b'. 35 36 Additional constraint on the input: the sum of values of $n$ over all test cases does not exceed $2 \cdot 10^5$. 37 38 Output 39 40 For each test case, print the answer as follows: 41 42 If in order to make the number of letters 'a' and 'b' equal, it is necessary to remove all letters from the string $s$, output $-1$. 43 44 Otherwise, output the minimum number of consecutive letters that Monocarp needs to remove from his string $s$ so that the number of letters 'a' and 'b' becomes equal. 45 46 Example 47 48 Input 49 50 ``` 51 5 52 53 5 54 55 bbbab 56 57 6 58 59 bbaaba 60 61 4 62 63 aaaa 64 65 12 66 67 aabbaaabbaab 68 69 5 70 71 aabaa 72 ``` 73 74 Output 75 76 ``` 77 3 78 79 0 80 81 -1 82 83 2 84 85 -1 86 ``` 87 88 Note 89 90 In the first example, Monocarp needs to remove the first three letters from his string. After that, his string will become "ab". In this string, there is one letter 'a' and one letter 'b'. 91 92 In the second example, the given string has three letters 'a' and three letters 'b', so nothing needs to be removed. 93 94 In the third example, all letters of the string need to be removed, as there are no letters 'b', so $-1$ should be printed. 95 96 In the fourth example, Monocarp can, for example, remove the fifth and sixth letters from his string. Then his string will become "aabbabbaab". In this string, there are five letters 'a' and five letters 'b'. 97 98 In the fifth example, all letters of the string need to be removed to make the number of letters 'a' and 'b' equal, so $-1$ should be printed.