ARC224 E - ABC|AB|A

考え方

削除可能な文字列はすべて 'A' から始まっている。
よって、各 'A' の削除順を考えればよい。

"AABB" のような場合、先に後ろの 'A' を使って "AB" を削除しなければならない。
先に前の 'A' を使うと、最後尾の 'B' が削除できなくなってしまう。
このように、複数の 'A' に対し、前を先に削除すると最善を逃すケースが存在する。

では一方で、後ろを先に削除して困る例はあるかというと、存在しない。
絶対に逆順に削除して全く同じ結果を作ることができる。
ということで、'A' はすべて後ろから順に削除していけばよい。

また、"ABC" を消せるのに "AB" だけや "A" だけ削除するのも、特に優位性はない。
よって、非常に単純な以下のような貪欲で解ける。

• 文字列を後ろから $1$ 文字ずつ見ていく
• 'A' があったら、それを削除
• 'A' 削除時、その後ろに 'B' があったらそれも削除
• 'B' 削除時、その後ろに 'C' があったらそれも削除

最終的に残った文字列の長さが答えで、計算量は $O\left(\sum N\right)$。

入力例1での動作

$1$ つ目のテストケースのみ考える。

入力を受け取る。

s: CAABCB

s を右から見て、残る予定の文字列を逆順に t に入れていく。

まず、右端の B を t に移す。

s: CAABC
t: B

次に、C, B を順に t に移す。

s: CAA
t: BCB

次に、A を t に移す。
t の末尾から A, B, C と並んでいるので、これらを削除する。

s: CA
t: B

次の A を t に移す。
t の末尾から A, B と並んでいるので、これらを削除する。

s: C
t:

最後に、C を t に移す。

s:
t: C

最終的な t の長さは $1$ なので、答えは $1$ である。

注意点

特になし。

別解

特になし。