Deletion 2

A terminal string has no two adjacent different characters. Therefore it is either empty or consists of only one kind of character.

Lemma 1. A string $W$ of length $m$ can be completely deleted if and only if $m$ is even and every character appears at most $m/2$ times.

Proof

Whenever one character is deleted, a different character must be deleted with it, so necessity is immediate.

For sufficiency, use induction on $m$. If some character appears exactly $m/2$ times, delete a pair at a boundary between that character and another character. Otherwise, delete any adjacent pair of different characters. In both cases the remaining string satisfies the same condition.

Fix a character $X$ and consider terminal strings consisting only of $X$. Let the other two characters be $Y,Z$.

After choosing the occurrences of $X$ that remain, every segment between them and at both ends must disappear.

Lemma 2. It is enough to require that, in each such segment, both $Y$ and $Z$ appear at most half of the segment length. This does not change the maximum possible number of surviving $X$'s.

Proof

Every completely deletable segment satisfies this condition by Lemma 1.

Conversely, if a segment satisfying this condition also contains at most half $X$, the whole segment can be deleted by Lemma 1. If $X$ appears more than half the time, every $Y,Z$ can be deleted together with an $X$, leaving only $X$'s in that segment.

Hence, if $k$ occurrences of $X$ can remain under this condition, actual operations can leave at least $k$ copies of $X$. Therefore the maximum is unchanged.

Let this maximum be $M_X$.

Let $Y_i,Z_i$ be the numbers of $Y,Z$ in $S[1\ldots i]$. For a position $i$ with $S_i=X$, define $u_i=i-2Z_i$ and $v_i=i-2Y_i$.

Two occurrences $j<i$ of $X$ can be consecutive survivors exactly when the segment between them satisfies Lemma 2. This is equivalent to $u_j<u_i$, $v_j<v_i$, and $j\not\equiv i\pmod 2$.

A first surviving $X$ at position $i$ must satisfy that $i$ is odd, $u_i>0$, and $v_i>0$. Let $U=N-2Z_N$ and $V=N-2Y_N$. A last surviving $X$ at position $i$ must satisfy $i\equiv N\pmod 2$, $u_i\le U$, and $v_i\le V$.

Let $dp_i$ be the maximum number of surviving $X$'s when position $i$ is the last survivor. A predecessor $j$ must satisfy $j<i$, $u_j<u_i$, $v_j<v_i$, and have the opposite parity. This is a three-dimensional dominance DP on the index, $u$, and $v$, so CDQ divide and conquer finds $M_X$ in $O(N\log^2 N)$.

Lemma 3. Among positions with $S_i=X$, if $u_j<u_i$ and $v_j<v_i$, then $j<i$ always holds.

Proof

Let $X_i$ be the number of $X$ in $S[1\ldots i]$. Then $u_i+v_i=2X_i$.

Among positions containing $X$, $X_i$ is strictly increasing in their original order. Thus $u_j<u_i$ and $v_j<v_i$ imply $u_j+v_j<u_i+v_i$, so $X_j<X_i$ and therefore $j<i$.

By Lemma 3, the index condition is unnecessary. Process the points by $u$ and maintain the dominance maximum by $v$ with a Fenwick Tree. Keep the two parities separately. This finds $M_X$ in $O(N\log N)$.

Repeat this for $X=\texttt{A},\texttt{B},\texttt{C}$.

Suppose $X$ appears $x$ times in the whole string. If the terminal string is $X^k$, then $k\equiv N\pmod 2$ because every operation removes two characters. Also, deleting one $X$ requires one non-$X$, so $k\ge 2x-N$.

Thus the smallest positive possible length is $L_X=\max(2x-N,1)$ when $N$ is odd, and $L_X=\max(2x-N,2)$ when $N$ is even.

Lemma 4. If $M_X>0$, the possible lengths are exactly $L_X,L_X+2,\ldots,M_X$.

Proof

Suppose $X^k$ is reachable and $k>L_X$. Let $G_0,G_1,\ldots,G_k$ be the completely deleted segments around the $k$ surviving $X$'s.

Let $m_r$ be the length of $G_r$ and $x_r$ the number of $X$ in it. Then $d_r=m_r/2-x_r$ is a nonnegative integer. Also, $\sum d_r=(N-2x+k)/2>0$, so some $d_r$ is positive.

Delete two consecutive surviving $X$'s so that the merged segment contains such a segment. In the merged segment, all three characters appear at most half of its length. By Lemma 1, the whole merged segment can be deleted, so $X^{k-2}$ is also reachable.

Repeating this gives every length $L_X,L_X+2,\ldots,M_X$.

Therefore, if $M_X>0$, the number of terminal strings consisting only of $X$ is $(M_X-L_X)/2+1$.

By Lemma 1, the empty string is reachable exactly when $N$ is even and $2\max(\#A,\#B,\#C)\le N$. Add the counts for the three characters, and add one more if the empty string is reachable.

Therefore, the overall time complexity is $O(N\log N)$.