## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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.

### 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 YESyesYes,

Solution Click Below:-  👉
👇👇👇👇👇

and yEs are all considered the same.

### 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 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.