← 返回题目列表

Codeforces · 1807/C

C. 查找和替换

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

给您一个由小写拉丁字符组成的字符串 $$$s$$$。在操作中,您可以获取一个字符并将所有出现的该字符替换为 $$$\texttt{0}$$$ 或替换所有出现的该字符为 $$$\texttt{1}$$$。

是否可以执行一定次数的移动,以便生成的字符串是交替的二进制字符串$$$^{\dagger}$$$?

例如,考虑字符串 $$$\texttt{abacaba}$$$。您可以执行以下操作:

- 将 $$$\texttt{a}$$$ 替换为 $$$\texttt{0}$$$。现在字符串是$$$\color{red}{\texttt{0}}\texttt{b}\color{red}{\texttt{0}}\texttt{c}\color{red}{\texttt{0}}\texttt{b}\color{red}{\texttt{0}}$$$。
- 将 $$$\texttt{b}$$$ 替换为 $$$\texttt{1}$$$。现在字符串是 $$${\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}\texttt{c}{\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}$$$。
- 将 $$$\texttt{c}$$$ 替换为 $$$\texttt{1}$$$。现在字符串是 $$${\texttt{0}}{\texttt{1}}{\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}{\texttt{1}}{\texttt{0}}$$$。这是一个交替的二进制字符串。

$$$^{\dagger}$$$交替二进制字符串是 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$ 的字符串,使得没有两个相邻位相等。例如,$$$\texttt{01010101}$$$、$$$\texttt{101}$$$、$$$\texttt{1}$$$ 是交替二进制字符串,但 $$$\texttt{0110}$$$、$$$\texttt{0a0a0}$$$、$$$\texttt{10100}$$$ 不是。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。测试用例的描述如下。

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

每个测试用例的第二行包含一个由 $$$n$$$ 小写拉丁字符组成的字符串 - 字符串 $$$s$$$。

输出

对于每个测试用例,如果可以将字符串变成交替的二进制字符串,则输出“YES”(不带引号),否则输出“NO”(不带引号)。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

8
7
abacaba
2
aa
1
y
4
bkpt
6
ninfia
6
banana
10
codeforces
8
testcase

输出 #1

YES
NO
YES
YES
NO
YES
NO
NO

注意

第一个测试用例在语句中进行了解释。

在第二个测试用例中,唯一可能的二进制字符串是 $$$\texttt{00}$$$ 和 $$$\texttt{11}$$$,它们都不是交替的。

在第三个测试用例中,您可以创建 $$$\texttt{1}$$$,它是一个交替的二进制字符串。