← 返回题目列表

Codeforces · 1494/A

A. ABC 字符串

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

给定一个字符串 $$$a$$$,由 $$$n$$$ 个字符组成,$$$n$$$ 是偶数。对于从$$$1$$$到$$$n$$$的每个$$$i$$$,$$$a_i$$$是“A”、“B”或“C”之一。

括号序列是仅包含字符“(”和“)”的字符串。正则括号序列是通过在序列的原始字符之间插入字符“1”和“+”,可以将括号序列转化为正确的算术表达式。例如,括号序列“()()”和“(())”是正规的(结果表达式是:“(1)+(1)”和“((1+1)+1)”),而“)(”、“(”和“)”则不是。

您想要查找由 $$$n$$$ 字符组成的字符串 $$$b$$$,如下所示:

- $$$b$$$ 是常规括号序列;
- 如果对于某些 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$) $$$a_i=a_j$$$,则 $$$b_i=b_j$$$。

换句话说,您希望将所有出现的“A”替换为相同类型的括号,然后将所有出现的“B”替换为相同类型的括号,并将所有出现的“C”替换为相同类型的括号。

你的任务是确定这样的字符串 $$$b$$$ 是否存在。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例的描述。

每个测试用例的唯一行包含字符串 $$$a$$$。 $$$a$$$ 仅由大写字母“A”、“B”和“C”组成。令 $$$n$$$ 为 $$$a$$$ 的长度。保证 $$$n$$$ 是偶数且 $$$2 \le n \le 50$$$。

输出

对于每个测试用例,如果存在这样的字符串 $$$b$$$ ,则打印“YES”:

- $$$b$$$ 是常规括号序列;
- 如果对于某些 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$) $$$a_i=a_j$$$,则 $$$b_i=b_j$$$。

否则,打印“NO”。

您可以按您想要的任何大小写打印每个字母(例如,字符串 yEs、yes、Yes 和 YES 都被识别为肯定答案)。

示例

输入 #1

4
AABBAC
CACA
BBBBAC
ABCA

输出 #1

YES
YES
NO
NO

注意

在第一个测试用例中,可能的字符串 $$$b$$$ 是“(())()”。

在第二个测试用例中,可能的字符串 $$$b$$$ 之一是“()()”。