codeforces-scrape

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

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.