Hints: https://atcoder.jp/contests/agc066/editorial/9708

[1] Structure of optimal solutions

Let \(T\) denote the string after operations.

If we add a B at the end of both \(S\) and \(T\), then \(T\) can be seen as a sequence of B and AB.

Let us think about the structure of the optimal \(T\) by considering the operation of swapping adjacent B and AB in \(T\).

Assume \(T\) is the optimal solution. For a part BAB in \(T\) where B and AB are arranged in this order, if the initial position of this A is to the left of this position, you can reduce the cost by swapping these AB and B. For a part ABB in \(T\) where AB and B are arranged in this order, if the initial position of this A is to the right of this position, you can reduce the cost by swapping and AB and B.

Then, it can be seen that in the optimal solution \(T\), when decomposed into AB and B, no A passes through the positions before and after B.

[2] Calculating the answer with dynamic programming

Based on the observations above, let us design a solution using dynamic programming.

\(\mathrm{dp}[i]\) is defined as the minimum cost to create a string of length \(i\) consisting of AB and B from only the first \(i\) characters of \(S\) (without swapping the \(i\)-th and \((i+1)\)-th characters).

First, if the \(i\)-th character of \(S\) is B, there is a transition \(\mathrm{dp}[i] \leftarrow \mathrm{dp}[i-1]\).

For the part where we arrange ABs, do the following. First, define \(\mathrm{sum}[i]\) as the number of Bs minus the number of As among the first \(i\) characters of \(S\). Then, when \(i<j\) and \(\mathrm{sum}[i] = \mathrm{sum}[j]\), you should make a transition from \(\mathrm{dp}[i]\) to \(\mathrm{dp}[j]\) for arranging ABs in between.

For \(i, k, j\) such that \(i<k<j\) and \(\mathrm{sum}[i] = \mathrm{sum}[k]=\mathrm{sum}[j]\), the transition from \(\mathrm{dp}[i]\) to \(\mathrm{dp}[j]\) can be decomposed into transitions from \(\mathrm{dp}[i]\) to \(\mathrm{dp}[k]\) and from \(\mathrm{dp}[k]\) to \(\mathrm{dp}[j]\), so you only need to consider transitions where such \(k\) does not exist.

As a result, both the number of states and the number of transitions in DP are \(O(N)\).

For cases where there is no \(k\) such that \(i<k<j\) and \(\mathrm{sum}[i] = \mathrm{sum}[k]=\mathrm{sum}[j]\), it is also easy to see that for the arranged ABs in between, there cannot be both As coming from the left and from the right. Therefore, the cost of each transition can be calculated in \(O(1)\) time with appropriate precomputation of cumulative sums.