题目描述

给定一个由小写拉丁字母组成的字符串 $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" 都被视为正确答案）。

样例

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

YES
NO
YES
YES
NO
YES
NO
NO

样例说明

第一个测试用例的解释见题面。

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

第三个测试用例中，可以得到 $\texttt{1}$，它是一个交替二进制字符串。

由 ChatGPT 4.1 翻译

来源

Codeforces 1807C，英文题名 Find and Replace。