CF 1807C - Find and Replace

You are given a string s consisting of lowercase Latin characters. In an operation, you can take a character and replace all occurrences of this character with 0 or replace all occurrences of this character with 1.

Is it possible to perform some number of moves so that the resulting string is an alternating binary string†?

(资料图片)

For example, consider the string abacaba. You can perform the following moves:

Replace a with 0. Now the string is 0b0c0b0.

Replace b with 1. Now the string is 010c010.

Replace c with 1. Now the string is 0101010. This is an alternating binary string.†

An alternating binary string is a string of 0s and 1s such that no two adjacent bits are equal. For example, 01010101, 101, 1 are lternating binary strings, but 0110, 0a0a0, 10100 are not.

Input

The input consists of multiple test cases. The first line contains an integer t (1≤t≤100) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer n (1≤n≤2000) -the length of the string s.

The second line of each test case contains a string consisting of n

lowercase Latin characters — the string s.

Output

For each test case, output "YES" (without quotes) if you can make the string into an alternating binary string, and "NO" (without quotes) otherwise.

You can output the answer in any case (for example, the strings “”yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

----------------------------------

给定一个由小写拉丁字符组成的字符串 s。 在运算中，您可以获取一个字符，并将所有出现的该字符替换为 0，或者将所有出现的该字符替换为 1。

是否可以执行一定次数的移动以使结果字符串成为交替的二进制字符串†？

例如，考虑字符串 abacaba。 您可以执行以下操作：

将 a 替换为 0。现在字符串为 0b0c0b0。

将 b 替换为 1。现在字符串为 010c010。

将 c 替换为 1。现在字符串是 0101010。这是一个交替的二进制字符串。†

交替的二进制字符串是由 0 和 1 组成的字符串，任何两个相邻位都不相等。 例如，01010101、101、1 是交替二进制字符串，但 0110、0a0a0、10100 不是。

输入

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

每个测试用例的第一行包含一个整数n（1≤n≤2000）-字符串s的长度。

每个测试用例的第二行包含一个由n组成的字符串

小写拉丁字符 — 字符串 s。

输出

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

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

------------------

用hashmap保存每个字母对应的值，如果遇到没有的，根据flag是去判断，如果出错了，就返回false，没问题就输出yes

下面是代码：

关键词：