Official Editorial (C++)

Explanation

The somewhat weird observation we have to make here is that the replacement process can be thought of as Bs "eating" As and leaving Cs where they once were.

This process is shown most clearly in the 5th sample test case:

AAAAAAB
AAAAABC
AAAABCC
...
BCCCCCC

Since Bs leave Cs behind when they eat an A, they have to choose one direction and commit to it.

With that, all we need is this info:

1. How many "runs" of As there are and their sizes
2. How many Bs there are that are adjacent to a run of As.

Notice that since the initial string can only alternate between As and Bs, there can be at most one more run of As then there are available Bs.

If this is the case, we have to give up the smallest run of As that occurs. If not, though, we can output the sum of all the runs of As- that is, the total number of As in the string.

Implementation

Time Complexity: $\mathcal{O}(|s|)$

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {
	int test_num;

Copy
import java.io.*;
import java.util.*;

public class ABBCorBACB {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			// Add an X for convenience in the below for loop
			String str = read.readLine() + 'X';

Copy
from itertools import groupby

for _ in range(int(input())):
	string = input()

	b_amts = 0
	a_runs = []
	for char, amt in groupby(string):
		if char == "A":
			a_runs.append(len(list(amt)))