Casimir's String Solitaire
Contest: Codeforces Round 744 (Div. 3)
Difficulty rating: 800
Tags: math, strings

Casimir has a string $$$s$$$ which consists of capital Latin letters 'A', 'B', and 'C' only. Each turn he can choose to do one of the two following actions:

- he can either erase exactly one letter 'A' and exactly one letter 'B' from arbitrary places of the string (these letters don't have to be adjacent);
- or he can erase exactly one letter 'B' and exactly one letter 'C' from arbitrary places in the string (these letters don't have to be adjacent).

Therefore, each turn the length of the string is decreased exactly by $$$2$$$. All turns are independent so for each turn, Casimir can choose any of two possible actions.

For example, with $$$s$$$ $$$=$$$ "ABCABC" he can obtain a string $$$s$$$ $$$=$$$ "ACBC" in one turn (by erasing the first occurrence of 'B' and the second occurrence of 'A'). There are also many other options for a turn aside from this particular example.

For a given string $$$s$$$ determine whether there is a sequence of actions leading to an empty string. In other words, Casimir's goal is to erase all letters from the string. Is there a way to do this?

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case is described by one string $$$s$$$, for which you need to determine if it can be fully erased by some sequence of turns. The string $$$s$$$ consists of capital letters 'A', 'B', 'C' and has a length from $$$1$$$ to $$$50$$$ letters, inclusive.

Output format:
Print $$$t$$$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be YES if there is a way to fully erase the corresponding string and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes, and YES will all be recognized as positive answers).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
6
ABACAB
ABBA
AC
ABC
CABCBB
BCBCBCBCBCBCBCBC

Example output:
NO
YES
NO
NO
YES
YES

Editorial:
Note that no matter which action is chosen, after this action is performed
• exactly one letter 'B' is erased from the string
• exactly two letters in total are erased from the string
Let's denote the length of the string $$$s$$$ by $$$n$$$. If $$$n$$$ is odd, then described turns can not erase all the characters from the strings, because if he is deleting two letters on each turn, the length will always remain odd. For example, if the original length of the string is $$$5$$$, then after one turn it will be equal to $$$3$$$, and after two moves it will be equal to $$$1$$$ in which case the next turn is impossible. Thus, if the length of the row is odd, the answer is NO.
If $$$n$$$ is even, it will take exactly $$$\frac{n}{2}$$$ steps to erase all characters from the string. Since each action removes exactly one letter 'B' from the string, the string can become empty only if there are exactly $$$\frac{n}{2}$$$ letters 'B'.
Let us show that this condition is sufficient, that is, if a string has exactly half of the letters equal to 'B', then there always exists a sequence of actions leading to an empty string. Indeed, if a string of length $$$n$$$ has exactly $$$\frac{n}{2}$$$ letters 'B', exactly $$$x$$$ letters 'A' and exactly $$$y$$$ letters 'C', then $$$x + y = n - \frac{n}{2} = \frac{n}{2}$$$. Then Casimir can make $$$x$$$ moves of the first type, each time removing the first occurrence of 'B' and the first occurrence of 'A', and $$$y$$$ moves of the second type, each time removing the first occurrence of 'B' and the first occurrence of 'C'. After $$$x + y = \frac{n}{2}$$$ such moves, the string will become empty.
Thus, checking that the number of letters 'B' in the string is exactly half of its length was enough to solve the problem.