← 返回题目列表

AtCoder · agc066_c

C. 删除 AAB 或 BAA

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

分数: 800 点

问题陈述

给你一个字符串 S 由字符组成 A 和 B.

在此字符串上,您可以重复执行以下操作:

  • 选择三个连续的字符 S 等于 AAB or BAA,然后删除这三个字符 S (删除后,剩余字符连接)。

查找可以执行此操作的最大次数。

T 给出了测试用例;解决它们中的每一个。

约束

  • 1\leq T\leq 10^5
  • S 是一个由以下组成的字符串 A 和 B.
  • 1\leq |S|\leq 10^6
  • 总和 |S| 单个输入中的所有测试用例最多 10^6.

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

S

输出

打印 T 行。的 i- 第行应包含可以执行的最大操作数 i- 第一个测试用例。


示例输入 1

10
AABAAAB
BAAAAABBA
A
B
ABA
BAA
AAAAAA
AAAABB
AABABBAABBABAAAABBAA
BBAAAAABAAAAABABAABA

示例输出 1

2
3
0
0
0
1
0
2
5
6

对于第一个和第二个测试用例,以下是执行最大操作数的可能方法:

  • AABAAAB → AAAB → A
  • BAAAAABBA → BAAABA → BAA →(空字符串)