codeforces-scrape

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

1428C.md (1735B)


      1 Source: https://codeforces.com/problemset/problem/1428/C
      2 
      3 C. ABBB
      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 Zookeeper is playing a game. In this game, Zookeeper must use bombs to bomb a string that consists of letters 'A' and 'B'. He can use bombs to bomb a substring which is either "AB" or "BB". When he bombs such a substring, the substring gets deleted from the string and the remaining parts of the string get concatenated.
     22 
     23 For example, Zookeeper can use two such operations: AABABBA $\to$ AABBA $\to$ AAA.
     24 
     25 Zookeeper wonders what the shortest string he can make is. Can you help him find the length of the shortest string?
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 20000)$  — the number of test cases. The description of the test cases follows.
     30 
     31 Each of the next $t$ lines contains a single test case each, consisting of a non-empty string $s$: the string that Zookeeper needs to bomb. It is guaranteed that all symbols of $s$ are either 'A' or 'B'.
     32 
     33 It is guaranteed that the sum of $|s|$ (length of $s$) among all test cases does not exceed $2 \cdot 10^5$.
     34 
     35 Output
     36 
     37 For each test case, print a single integer: the length of the shortest string that Zookeeper can make.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 3
     45 AAA
     46 BABA
     47 AABBBABBBB
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 3
     54 2
     55 0
     56 ```
     57 
     58 Note
     59 
     60 For the first test case, you can't make any moves, so the answer is $3$.
     61 
     62 For the second test case, one optimal sequence of moves is BABA $\to$ BA. So, the answer is $2$.
     63 
     64 For the third test case, one optimal sequence of moves is AABBBABBBB $\to$ AABBBABB $\to$ AABBBB $\to$ ABBB $\to$ AB $\to$ (empty string). So, the answer is $0$.