← 返回题目列表

AtCoder · arc224_e

E. 字母串 ABC、AB、A

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

分数: 500 点

问题陈述

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

您可以执行以下操作零次或多次。

  • 选择一个子串(连续子序列) S 即 A, AB,或 ABC,然后将其删除。剩余的字符被连接起来,保留它们的顺序。

找出以下的最小可能长度 S 最后。

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

约束

  • T 是介于 1 和 10^5,包括在内。
  • S 是一个由以下组成的字符串 A, B,和 C 长度介于 每个输入中的 1 和 10^6,包括在内。
  • 总和 一个输入文件中的 |S| 最多为 10^6.

输入

输入由标准输入按以下格式给出,其中 \mathrm{case}_i 表示 i-第一个测试用例:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

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

S

输出

输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

5
CAABCB
B
AAABBC
AABBCC
CABCCBCBAABCBBBAABAABACABBC

示例输出 1

1
1
0
1
7

此输入包含五个测试用例。

对于第一个测试用例,我们可以执行如下操作。

  • 选择并删除第三个到第五个字符 S= CAABCB。手术后, S 变为 CAB.
  • 选择并删除第二个到第三个字符 S= CAB。手术后, S 变为 C.
  • 无法执行进一步操作。 S= C 有长度 1,这是可实现的最小值。