# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Jeevan Jyot Singh

*Tejas Pandey*

**Tester:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

1173

# PREREQUISITES:

None

# PROBLEM:

Given a binary string S, in one move you can pick two indices and flip their values. Is it possible to make the final string a palindrome?

# EXPLANATION:

You might notice that performing an operation on two indices with two different values essentially swaps the values at these indices. This is already enough to make S into a palindrome whenever:

- N is odd; or
- N is even and contains both an even number of 0's and 1's

## Proof

When N is even, for S to be a palindrome both the 0's and the 1's must occur an even number of times, since each 0/1 is paired with another 0/1.

Itâ€™s fairly easy to see that if this condition holds, then just swapping 0's with 1's can make S into a palindrome. For example, if there are x occurrences of 0 and y of 1, then make the first x/2 and last x/2 characters of S 0 using swaps. This is a palindrome.

Further, any odd-length string can always be made a palindrome.

Either the 0's or the 1's must occur an odd number of times in an odd-length string; suppose itâ€™s the 0's.

Use one swap to make a 0 the middle character. Now, the remaining part of the string needs to be an even palindrome, and we satisfy the condition above so weâ€™re done.

As it turns out, these conditions are both necessary and sufficient.

## Proof

Note that the given operation doesnâ€™t actually change the parities of the 0's and 1's.

Let c_0 and c_1 be the respective counts. Then, one operation can change them as follows:

- c_0 \to c_0 + 2 and c_1 \to c_1 - 2 (flipping two 1's to 0)
- c_0 \to c_0 - 2 and c_1 \to c_1 + 2 (flipping two 0's to 1)
- Leave c_0 and c_1 unchanged (swapping a 0 and a 1)

All three cases donâ€™t change the parities. However, our earlier conditions only depended on the parities of c_0 and c_1. So, those cases are both necessary and sufficient.

Thus, the final solution is as follows: compute c_0 and c_1, the counts of 0 and 1 in the string. Then,

- If both c_0 and c_1 are odd, the answer is â€śNoâ€ť.
- Otherwise, the answer is â€śYesâ€ť.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
s = input()
z, o = s.count('0'), s.count('1')
if z%2 == 1 and o%2 == 1:
print('NO')
else:
print('YES')
```