← 返回题目列表

AtCoder · abc447_d

D. 采取 ABC 2

中文机器翻译题面 查看原题

分数: 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