Palindrome Flipping Codechef Solution

Problem

Chef has a binary string $S$ of length $N$.

In one operation, Chef can:

• Select two indices $i$ and $j$ $(1\le i,j\le N)$ and flip S_iSi​ and S_jSj​. (i.e. change $0$ to $1$ and $1$ to $0$)

For example, if $S=10010$ and chef applys operation on $i=1$ and $j=3$ then: \underline{1}0\underline{0}10 \rightarrow 001101​00​10→00110.

Find if it is possible to convert $S$ to a palindrome by applying the above operation any (possibly zero) number of times.

Note: A string is called a palindrome if it reads the same backwards and forwards, for e.g. $10001$ and $0110$ are palindromic strings.

Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ — the length of the binary string $S$.
• The second line of each test case contains a binary string $S$ of length $N$ containing $0$s and $1$s only.

Output Format

For each test case, output YES if it is possible to convert $S$ to a palindrome. Otherwise, output NO.

You can print each character of the string in uppercase or lowercase. For example, the strings YES, yes, Yes, and yEs are all considered the same.

Constraints

Sample 1:

3
6
101011
2
01
7
1110000

YES
NO
YES

Explanation:

Test case 1: We can perform the following operation:

• Select $i=3$ and $j=5$. Then 10\underline{1}0\underline{1}1 \rightarrow 100001101​01​1→100001, which is a palindrome.

Test case 2: It can be proven that we can not make $S$ a palindrome using the given operation.

Test case 3: We can perform the following operations:

• Select $i=4$ and $j=5$. Then 111\underline{0}\underline{0}00 \rightarrow 11111001110​0​00→1111100
• Select $i=6$ and $j=7$. Then 11111\underline{0}\underline{0} \rightarrow 1111111111110​0​→1111111, which is a palindrome.