ABBC or BACB
Contest: Codeforces Round 898 (Div. 4)
Difficulty rating: 1500
Tags: constructive algorithms, greedy

You are given a string $$$s$$$ made up of characters $$$\texttt{A}$$$ and $$$\texttt{B}$$$. Initially you have no coins. You can perform two types of operations:

- Pick a substring$$$^\dagger$$$ $$$\texttt{AB}$$$, change it to $$$\texttt{BC}$$$, and get a coin.
- Pick a substring$$$^\dagger$$$ $$$\texttt{BA}$$$, change it to $$$\texttt{CB}$$$, and get a coin.

$$$^\dagger$$$ A substring of length $$$2$$$ is a sequence of two adjacent characters of a string.

Input format:
The input consists of multiple test cases. The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The only line of each test case contains the string $$$s$$$ ($$$1 \leq |s| \leq 2 \cdot 10^5$$$). All characters of $$$s$$$ are either $$$\texttt{A}$$$ or $$$\texttt{B}$$$.

The sum of the lengths of $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the maximum number of coins you can obtain.

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

Note:
In the first test case you can perform the following operations to get $$$2$$$ coins: $$$$$$\color{red}{\texttt{AB}}\texttt{BA} \to \texttt{BC}\color{red}{\texttt{BA}} \to \texttt{BCCB}$$$$$$

In the second test case you can perform the following operation to get $$$1$$$ coin: $$$$$$\color{red}{\texttt{AB}}\texttt{A} \to \texttt{BCA}$$$$$$

In the third test case you can perform the following operations to get $$$3$$$ coins: $$$$$$\color{red}{\texttt{BA}}\texttt{ABA} \to \texttt{CBA}\color{red}{\texttt{BA}} \to \texttt{C}\color{red}{\texttt{BA}}\texttt{CB} \to \texttt{CCBCB}$$$$$$

Example input:
8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA

Example output:
2
1
3
1
6
2
0
0

Editorial:
Preface
Before we get into the editorial, I want to make a note that this type of problem is not traditional for Div. 4 on purpose, and is a lot more ad-hoc than usual. My goal was to make a sort of "introductory" ad-hoc problem, and I hope you enjoyed it. The editorial is a bit long, mainly because I want to go into a lot of detail regarding how to approach such ad-hoc problems, since usually most Div. 4 problems are unlike this, and instead focused on noticing and implementing the correct algorithm. I don't think anyone solving the problem will actually go through all this detail explicitly, but I wanted to provide a very explicit walk-through for anyone not knowing how to start.
But I think ad-hoc skills are important for Codeforces especially, hence this problem. Maybe you'll see more soon. ;)                                                                                                                                                                                                                              Analyzing the situation
Let's think about how we can repeatedly use the operations first. If we have a string $$$\texttt{AAAB}$$$, then we can do the operations $$$\texttt{AAAB} \to \texttt{AABC} \to \texttt{ABCC} \to \texttt{BCCC}$$$. Similarly, if we have a string $$$\texttt{BAAA}$$$, then we can do the operations $$$\texttt{BAAA} \to \texttt{CBAA} \to \texttt{CCBA} \to \texttt{CCCB}$$$.
In a sense, it's useful to think of the $$$\texttt{B}$$$ as "eating" the $$$\texttt{A}$$$s in a sense: whenever a $$$\texttt{B}$$$ is next to an $$$\texttt{A}$$$, it eats covers it and eats it, and then it moves on. Note that $$$\texttt{B}$$$ cannot eat $$$\texttt{C}$$$s.
Let's replace the characters as follows: replace $$$\texttt{A}$$$ with $$$\texttt{.}$$$ and $$$\texttt{C}$$$ with $$$\texttt{_}$$$. Then, it's much clear what is going on. Here is a series of moves on the string $$$\texttt{BAAABA}$$$, which becomes $$$\texttt{B...B.}$$$ after the replacing: $$$$$$\texttt{B...B.} \to \texttt{_B..B.} \to \texttt{__B.B.} \to \texttt{___BB.} \to \texttt{___B_B}$$$$$$
Now you can see how each $$$\texttt{B}$$$ is eating all the dots in one direction (it can't travel over blank spaces represented by $$$\texttt{_} = \texttt{C}$$$).                                                                                                                                                                                                                              Solving the problem
Okay, we have this intuition, how to solve the problem now? We need to eat the maximum number of dots ($$$\texttt{A}$$$s in the original string), since $$$\texttt{B}$$$s cannot eat anything else. Note that for each $$$\texttt{B}$$$, it can eat all the $$$\texttt{A}$$$s to its left or to its right, but not both; one it leaves its original spot, it is stuck on that side: $$$$$$\texttt{..B.} \to \texttt{.B_.} \to \texttt{B__.}$$$$$$ but the $$$\texttt{B}$$$ cannot reach the rightmost dot ever. This small example actually gives us a clue: for each $$$\texttt{B}$$$, let's count the number of $$$\texttt{A}$$$s on either side, and pick the largest one. This might work, but note that multiple $$$\texttt{B}$$$s may be able to reach the same dot.
This is where our original string comes into play. Suppose our original string starts with $$$\texttt{B}$$$, so it must be of the form $$$$$$\texttt{B} \underbrace{\texttt{A} \dots \texttt{A}}_{\text{some number, possibly } 0} \texttt{B} \underbrace{\texttt{A} \dots \texttt{A}}_{\text{some number, possibly } 0} \texttt{B} \underbrace{\texttt{A} \dots \texttt{A}}_{\text{some number, possibly } 0} \dots$$$$$$ Then each $$$\texttt{B}$$$ can simply eat all the $$$\texttt{A}$$$s after it, and so our answer is just the total number of $$$\texttt{A}$$$s. Similarly, if our string ends with $$$\texttt{B}$$$, then it must be of the form $$$$$$\dots\underbrace{\texttt{A} \dots \texttt{A}}_{\text{some number, possibly } 0} \texttt{B} \underbrace{\texttt{A} \dots \texttt{A}}_{\text{some number, possibly } 0} \texttt{B} \underbrace{\texttt{A} \dots \texttt{A}}_{\text{some number, possibly } 0} \texttt{B}$$$$$$ Then each $$$\texttt{B}$$$ can simply eat all the $$$\texttt{A}$$$s before it, and so our answer is just the total number of $$$\texttt{A}$$$s.
So we only have to look at the case where our string starts and ends with $$$\texttt{A}$$$, meaning our string looks something like: $$$$$$\underbrace{\texttt{A} \dots \texttt{A}}_{\text{some number, possibly } 0} \texttt{B} \underbrace{\texttt{A} \dots \texttt{A}}_{\text{some number, possibly } 0} \dots \,\,\,\,\,\,\,\, \texttt{B} \underbrace{\texttt{A} \dots \texttt{A}}_{\text{some number, possibly } 0}$$$$$$ If any of the $$$\texttt{B}$$$s are next to each other, like $$$$$$\underbrace{\texttt{A} \dots \texttt{A}}_{\text{some number, possibly } 0} \texttt{B} \texttt{B} \underbrace{\texttt{A} \dots \texttt{A}}_{\text{some number, possibly } 0}$$$$$$ then note that we can split the string into two strings, both of which either start or end with $$$\texttt{B}$$$, and so we can eat all the $$$\texttt{A}$$$s. So in this case, too, it is possible to get all the $$$\texttt{A}$$$s.
What's the only other case? Start and end with $$$\texttt{A}$$$, and there are no two $$$\texttt{B}$$$s next to each other. In this case, you can see there is one more "group" of $$$\texttt{A}$$$s than there are $$$\texttt{B}$$$s, but each $$$\texttt{B}$$$ can only get one group of $$$\texttt{A}$$$s. So we won't be able to get all of them.
What's the best we can do? Note that each $$$\texttt{B}$$$ can only get one group, if it goes left or right, so we can get all $$$\texttt{A}$$$s except one group. Now the answer is simply greedy: it is the total number of $$$\texttt{A}$$$s, minus the smallest group (since we want to get the most number of coins, we will take groups as large as possible).
You can also envision this as a sort of greedy: each $$$\texttt{B}$$$ takes the largest group available, and we stop once no more $$$\texttt{B}$$$s are free.
The time complexity for finding groups is $$$\mathcal{O}(n)$$$, so the whole solution runs in that time as well.