分数: 400 点
问题陈述
给你一个字符串 S 由三个字符组成 A, B,和 C.
定义一个操作如下:
选择一个元组 (i, j, k) 满意 1 \le i \lt j \lt k \le |S|, S_i =
A, S_j =B,和 S_k =C,并删除 i-th, j-th,以及 k- 第一个字符来自 S。其余字符按其原始顺序排列在左侧。
查找可以对字符串执行操作的最大次数 S.
约束
- 1 \le |S| \le 10^{6}
- S 是一个由以下组成的字符串
A,B,和C.
输入
输入由标准输入按以下格式给出:
S
输出
输出答案。
示例输入 1
ABACBCC
示例输出 1
2
该操作可以执行两次,如下所示:
-
对于
ABACBCC,执行操作 (i, j, k) = (1, 2, 7)。剩下的字符串是ACBC. -
对于
ACBC,执行操作 (i, j, k) = (1, 3, 4)。剩下的字符串是C.
该操作不能执行三次或多次,因此答案是 2。因此,输出 2.
示例输入 2
CBACBB
示例输出 2
0
示例输入 3
BBBAAABCBCBAACBBCAAC
示例输出 3
5