← 返回题目列表

Codeforces · 1632/A

A. ABC字符串

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

最近,179学校的学生开发了一种独特的算法,该算法以二进制字符串$$$s$$$作为输入。然而,他们很快发现,如果$$$s$$$的某些子串$$$t$$$是长度大于1的回文,算法将无法正常工作。学生们能否以某种方式重新排序 $$$s$$$ 的字符,以便算法能够正确地处理字符串?

二进制字符串是每个字符为 0 或 1 的字符串。

字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

回文是向后读与向前读相同的字符串。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,仅由字符 0 和 1 组成。

输出

对于每个测试用例,如果可以重新排序 $$$s$$$ 的字符以便不存在长度大于 1 的回文子串,则打印 YES(不区分大小写),否则打印 NO(不区分大小写)。

示例

输入 #1

4
1
1
2
10
2
01
4
1010

输出 #1

YES
YES
YES
NO

注意

在前三个测试用例中,给定的字符串不包含长度大于 1 的回文,因此答案为“是”。

在最后一个测试用例中,不可能对字符进行重新排序以使字符串不包含长度大于1的回文,因此答案是否定的。