D - Take ABC 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

A , B , C の 3 種類の文字のみからなる文字列 S が与えられます。

操作を以下のように定義します。

1 \le i \lt j \lt k \le |S| かつ S_i = A , S_j = B , S_k = C を満たす (i, j, k) の組を選び、S の i, j, k 文字目を取り除く。残った文字を元の順序を保ったまま左に詰める。

文字列 S に対して最大で何回操作を行うことができるかを求めてください。

制約

  • 1 \le |S| \le 10 ^{6}
  • S は A , B , C のみからなる文字列である

入力

入力は以下の形式で標準入力から与えられる。

S

出力

答えを出力せよ。

入力例 1

ABACBCC

出力例 1

2

以下のように操作をすることで 2 回操作できます。

  • ABACBCC に対して (i, j, k) = (1, 2, 7) として操作する。残った文字列は ACBC となる。

  • ACBC に対して (i, j, k) = (1, 3, 4) として操作する。残った文字列は C となる。

3 回以上操作することはできないため、答えは 2 となります。よって 2 と出力してください。

入力例 2

CBACBB

出力例 2

0

入力例 3

BBBAAABCBCBAACBBCAAC

出力例 3

5

Score : 400 points

Problem Statement

You are given a string S consisting of the three characters A, B, and C.

Define an operation as follows:

Choose a tuple (i, j, k) satisfying 1 \le i \lt j \lt k \le |S|, S_i = A, S_j = B, and S_k = C, and remove the i-th, j-th, and k-th characters from S. The remaining characters are packed to the left in their original order.

Find the maximum number of times the operation can be performed on string S.

Constraints

  • 1 \le |S| \le 10^{6}
  • S is a string consisting of A, B, and C.

Input

The input is given from Standard Input in the following format:

S

Output

Output the answer.

Sample Input 1

ABACBCC

Sample Output 1

2

The operation can be performed twice as follows:

  • For ABACBCC, perform the operation with (i, j, k) = (1, 2, 7). The remaining string is ACBC.

  • For ACBC, perform the operation with (i, j, k) = (1, 3, 4). The remaining string is C.

The operation cannot be performed three or more times, so the answer is 2. Thus, output 2.

Sample Input 2

CBACBB

Sample Output 2

0

Sample Input 3

BBBAAABCBCBAACBBCAAC

Sample Output 3

5