The problem is equivalent to taking non-overlapping (and not necessarily contiguous) subsequences ABC as many as possible.

Solution

The following greedy algorithm is valid. Intuitively, we “take ABC whenever we can take.”

Initialize integers \(A\), \(B\), and \(C\) with \(0\). (These represent the number of times A, B, and C were taken, respectively.)

For each \(i = 1, 2, \dots , N\), do the following:

• If \(S_i =\) A:

  Let \(A \leftarrow A + 1\).

• If \(S_i =\) B:

  Let \(B \leftarrow \min(A, B + 1)\).

• If \(S_i =\) C:

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

The final value of \(C\) is the answer.

Proof

Let \(A_i, B_i\), and \(C_i\) be the value of the variables \(A, B\), and \(C\) when step \(i\) in the greedy algorithm algorithm ends. Also, let \(a_i, b_i, c_i\) be the values in a solution. Since we are taking ABC as subsequences, we always have \(A_i \ge B_i \ge C_i\) and \(a_i \ge b_i \ge c_i\).

We will show that the following inequalities hold for all \(i\):

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

• Regarding A:

  The greedy algorithm always adopts A, so \(A_i \ge a_i\) for any solution.

• Regarding B:

  If the greedy algorithm did not pick B, then \(A_i = B_i\) at that point. In any solution, we must have \(a_i \ge b_i\) (because A is adopted prior to B), thus:

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

  Hence, \(B_i \ge b_i\).

• Regarding C:

  By the same discussions as B, we have \(C_i = B_i \ge b_i \ge c_i\).

Therefore, we have \(C_i \ge c_i\) for all \(i\); thus \(C_N \ge c_N\), which implies that the greedy algorithm above never underestimates the number of ABC that can be taken. This concludes the proof.

Sample code in 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)