/ 
Time Limit: 2 sec / Memory Limit: 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, andC.
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 isACBC. -
For
ACBC, perform the operation with (i, j, k) = (1, 3, 4). The remaining string isC.
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