問題を言い換えると「（連続するとは限らない）部分列で ABC であるもの」を重なりのないように、なるべく多く選ぶ問題となります。

解法

以下のような貪欲法が正当です。直感的には「採用できるなら採用する」をする方法です。

変数 \(A, B, C\) を \(0\) で初期化する。（それぞれ A, B, C の採用した個数を管理している）

\(i = 1, 2, \dots , N\) について順番に以下の処理をする。

• \(S_i =\) A のとき

  \(A \leftarrow A + 1\) とする

• \(S_i =\) B のとき

  \(B \leftarrow \min(A, B + 1)\) とする

• \(S_i =\) C のとき

  \(C \leftarrow \min(B, C+1)\)
  

最終的な \(C\) の値が答えとなる。

証明

ステップ \(i\) 終了時点における貪欲法の採用数を \(A_i, B_i, C_i\) とします。また、ある解における採用数を \(a_i, b_i, c_i\) とします。部分列として ABC を構成する性質から、\(A_i \ge B_i \ge C_i\) と \(a_i \ge b_i \ge c_i\) が常に成立していることに注意して下さい。

このとき、すべての \(i\) について以下の不等式が成り立つことを示します。

\[A_i \ge a_i, \quad B_i \ge b_i, \quad C_i \ge c_i\]

• A について

  貪欲法では A を常に採用します。したがって、どのような解に対しても \(A_i \ge a_i\) が常に成立します。

• B について

  貪欲法が B を採用できなかったならば、その時点で \(A_i = B_i\) が成り立っています。どのような解においても、（ A のほうが B より先に採用されるため） \(a_i \ge b_i\) が成立する必要があり、以下の式が成立します。

  \[B_i = A_i \ge a_i \ge b_i\]

  よって、\(B_i \ge b_i\) が成立します。

• C について

  B と同様の議論（ \(C_i = B_i \ge b_i \ge c_i\) ）が成立します。

以上より すべての \(i\) で \(C_i \ge c_i\) ですから、\(C_N \ge c_N\) も成立します。これは、上の貪欲がどのような採用方法よりも ABC の個数が小さくならないことを意味します。よって示されました。

Python の実装例

s = input()
a, b, c = 0, 0, 0
for i in s:
    if i == "A":
        a += 1
    if i == "B":
        b = min(a, b + 1)
    if i == "C":
        c = min(b, c + 1)
print(c)