Observations on the Problem

This problem can be viewed as a Tetris game with only dominoes and a field width of \(3\). The main differences are:

• Dominoes cannot be rotated.
• When placing a domino horizontally, there must be no gaps below it.
• The score is incremented by \(1\) whenever all the pieces are cleared.

Therefore, we will explain the procedure to determine the score of the operation sequence \(X\) corresponding to the string \(S\) using examples of dominoes. Specifically, getting \(h_1=h_2=h_3\) is called flattening.

Characteristics of \(S\)

For \(i=0,1,\dots ,N\), let \(a_i\) be the number of As and \(b_i\) be the number of Bs up to the \(i\)-th character of \(S\).

Next, let’s consider the conditions under which the sequence can be flattened when processing up to the \(i\)-th character of \(S\). From simple observations, we can see that:

• \(a_i+b_i\equiv 0\pmod 3\)
• \(b_i\equiv 0\pmod 2\)

Additionally, it is necessary that there are not too many Bs, specifically:

• \(b_i\le 2a_i\)

This is because there can be at most one horizontal domino per level.

Therefore, defining \(V_i=2a_i-b_i\) for \(i=0,1,\dots ,N\), the necessary conditions so far can be expressed as:

\[V_i\ge 0, V_i\equiv 0\pmod 6.\]

Similarly, for \(0\le i_1\lt i_2\lt \dots \lt i_k\le N\), the necessary conditions for the sequence to be flattened at each timing are:

\[0\le V_{i_1}\le V_{i_2}\le \dots \le V_{i_k}\ , V_{i_1}\equiv V_{i_2}\equiv\cdots\equiv V_{i_k}\equiv 0\!\!\!\!\pmod 6.\]

In fact, these conditions are also sufficient. That is, it is possible to construct an operation sequence that flattens the sequence at each timing.

Maximizing the Score

The problem becomes finding the longest subsequence \((V_{i_0},V_{i_1},V_{l_2},\dots ,V_{i_k})\) of \((V_0,V_1,\dots ,V_N)\) that satisfies:

• \(i_0=0\)
• \(V_{i_j}\equiv 0\pmod 6\ (j=0,1,\dots ,k)\)
• \(V_{i_j}\le V_{i_{j+1}}\ (j=0,1,\dots ,k-1)\)

This is essentially the longest non-decreasing subsequence problem, which can be solved in \(O(N\log N)\) time or so.

By reconstructing the answer subsequence \((V_{i_0},V_{i_1},V_{l_2},\dots ,V_{i_k})\), the problem can be broken down as follows:

For \(j=0,1,\dots ,k-1\), answer the following problem:

• Let \(T_j\) be the substring of \(S\) from the \((V_{i_j}+1)\)-th character to the \(V_{i_{j+1}}\)-th character.

• Construct an operation sequence corresponding to \(T_j\) that flattens the sequence when all characters are processed.

Constructing the Operation Sequence

Let \(T_j\) be redefined as \(S\), and let \(N\) be redefined as \(|S|\). Define \(V_i\) as mentioned earlier. Here, \(V_{N}\ge 0, V_N\equiv 0\pmod 6\) holds.

Construct an operation sequence \(X\) corresponding to \(S\) that flattens the sequence when all characters are processed.

The basic idea is that if A corresponds to 1 and B corresponds to 3, the score will not decrease. Specifically:

• When the \(i\)-th character of \(S\) is A, set the \(i\)-th character of \(X\) to 1.
  • This means placing a vertical domino on the left side.
• When the \(i\)-th character of \(S\) is B, set the \(i\)-th character of \(X\) to 3.
  • This means placing a horizontal domino on the right side.

While performing these operations, \(V_i\) represents the height \(h_1\) of the left side minus the height \(h_2\) of the center of the dominoes.

First, if \(V_N=0\), simply execute the basic idea. Below, assume \(V_N\ge 6\).

In this case, there are effectively three or more extra vertical dominoes. By aligning these extra vertical dominoes at the same height at an appropriate timing, we can reduce \(V_N\) by \(6\).

Focus on the smallest \(i\) where \(V_i\ge 4\). At this point, the \(i\)-th character of \(S\) is A.

When \(V_{i-1}=2\) and \(V_i=4\)

By setting the \(i\)-th character of \(X\) to 2 instead of 1, the heights of the left edge and the center of the domino align, and the height of the right edge is \(-2\) higher. Reversing this state horizontally reduce it to the state \(V_i=-2\).

When \(V_{i-1}=3\) and \(V_i=5\)

\(V_{i-2}\neq 4\) due to the minimality of \(i\), so \(V_{i-2}=1\). This means the \((i-1)\)-th character of \(S\) is also A. For these two consecutive As, setting the \((i-1)\)-th character of \(X\) to 2 instead of 1 and the \(i\)-th character of \(X\) to 3 instead of 1 reduce the state to \(V_i=-1\).

By handling these appropriately, we can obtain the desired \(X\).

Summary

Perform the following steps:

1. Compute \(V\) corresponding to \(S\) and solve the longest non-decreasing subsequence problem.
2. For the divided substrings, construct the corresponding operation sequence using the basic idea and reduction.

These processes can be performed in \(O(|S|\log |S|)\) time for each test case, ensuring sufficient speed.