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$.