[Solution] 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_i$ and $S_j$ . (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 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.

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.

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,

Solution Click Below:- 👉CLICK HERE👈

👇👇👇👇👇

and yEs are all considered the same.

Test case 1: We can perform the following operation:

Select $i = 3$ and $j = 5$ . Then $10\underline{1}0\underline{1}1 \rightarrow 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 1111100$
Select $i = 6$ and $j = 7$ . Then $11111\underline{0}\underline{0} \rightarrow 1111111$ , which is a palindrome.