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

[1] Strategy

We consider minimizing the number of remaining characters that we cannot delete. Let \(\mathrm{dp}[i]\) be the minimum possible number of characters that remain after performing operations on the first \(i\) characters of \(S\).

Roughly, the following calculations should be made:

• If the \(i\)-th character is not deleted: \(\mathrm{dp}[i+1]\leftarrow \mathrm{dp}[i]+1\).
• If characters from the \(i+1\)-th to the \(j\)-th are deleted: \(\mathrm{dp}[j]\leftarrow \mathrm{dp}[i]\).

Let us consider what the second transition looks like. To do this, we need to consider when operations can delete a string (turn it into an empty string).

---

[2] Conditions for a string to be deletable

The following holds:

• A string \(S\) can be turned into an empty string by operations if and only if \(S\) can be divided into substrings that satisfy the following: the number of As is twice the number of Bs, and the character at either the left or right end is B.

For simplicity, a string is called good when it satisfies the condition “the number of As is twice the number of Bs, and the character at either the left or right end is B.”

First, let us confirm the necessity.

Tracing the deletion operation in reverse, an \(S\) that can be turned into an empty string is obtained by repeatedly inserting AAB or BAA into an empty string. Therefore, it suffices to show that the stated condition is preserved by the insertion of AAB or BAA. To do this, it suffices to show that a good string with AAB or BAA inserted can be divided into good strings.

If the insertion is made between two characters of a good string, the character that was originally at one end remains at that end after the insertion, so it is fine. Otherwise, that is, if the insertion is at the beginning or end of a good string, the division into the original string and the inserted three characters provides a division into good strings.

This demonstrates the necessity.

Next, we show the sufficiency. To do this, it suffices to show that a good string can be turned into an empty string by operations. For this, it suffices to show that there is one operation that can be performed on a good string of length \(3\) or more such that it remains a good string after the operation.

The case of length \(3\) is obvious, so let us assume \(S\) is a good string of length \(6\) or more. One of the characters at the ends is B, but it suffices to prove the claim assuming that the left end is B. Suppose \(S\) contains \(n\) Bs and \(2n\) As.

Partitioning the second and subsequent characters of \(S\) by Bs divides it into \(n\) parts, one of which contains two or more As. It is possible to perform a deletion operation of AAB or BAA on this part, which shows that the operation can be performed while maintaining the condition that the first character is B. This demonstrates the sufficiency.

---

[3] Solution

Ultimately, it is clear that the following transitions should be considered in dynamic programming:

• \(\mathrm{dp}[i+1]\leftarrow \mathrm{dp}[i]+1\).
• When the substring from the \((i+1)\)-th to the \(j\)-th characters is a good string, \(\mathrm{dp}[j]\leftarrow \mathrm{dp}[i]\).

Let us consider how to calculate the latter.

Let \(x_i\) be the value obtained by subtracting twice the number of Bs from the number of As in the first \(i\) characters of \(S\), then the following transitions should be processed:

• If \(x_i=x_j\) and the \((i+1)\)-th character of \(S\) is B, then \(\mathrm{dp}[j]\leftarrow \mathrm{dp}[i]\).
• If \(x_i=x_j\) and the \(j\)-th character of \(S\) is B, then \(\mathrm{dp}[j]\leftarrow \mathrm{dp}[i]\).

For this, by maintaining the following for each \(x\):

• the minimum value of \(\mathrm{dp}[i]\) for \(i\) such that \(x_i = x\)
• the minimum value of \(\mathrm{dp}[i]\) for \(i\) such that \(x_i = x\) and the \(i\)-th character of \(S\) is B

all \(\mathrm{dp}[i]\) can be calculated in \(O(N)\) time overall.