Chef has a binary string S of length N. 

In one operation, Chef can:
Select two indices i and j (1 ≤ i, j ≤ N, i \ne j) 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 0s and 1s 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 ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$S$ contains $0$ and $1$ only.
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
6
101011
2
01
7
1110000

----- Sample Output 1 ------ 
YES
NO
YES

----- explanation 1 ------ 
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.

Difficulty: EASY
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	s = input()
	z = 0
	o = 0
	for i in s:
		if i == '0':
			z += 1
		else:
			o += 1
	if z % 2 != 0 and o % 2 != 0:
		print('NO')
	else:
		print('YES')


goals = int(input())
for distractions in range(goals):
	wife = int(input())
	life = input()
	(death, aim) = (0, 0)
	for j in range(wife):
		if life[j] == '1':
			death += 1
		else:
			aim += 1
	if wife % 2 == 0:
		if death % 2 and aim % 2:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


t = int(input())
for i in range(0, t):
	k = 0
	j = 0
	t1 = int(input())
	t2 = input()
	for i in range(t1):
		if t2[i] == '0':
			k += 1
		else:
			j += 1
	if k % 2 == 0 or j % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	a = 0
	b = 0
	for i in s:
		if i == '0':
			a += 1
		if i == '1':
			b += 1
	if a % 2 == 0 or b % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = 0
	b = 0
	for i in s:
		if i == '0':
			a += 1
		else:
			b += 1
	if a % 2 and b % 2:
		print('NO')
	else:
		print('YES')


t = int(input())
for z in range(t):
	n = int(input())
	ar = input()
	c0 = ar.count('0')
	c1 = ar.count('1')
	if c1 % 2 != 0 and c0 % 2 != 0:
		print('NO')
	else:
		print('YES')


n = int(input())
for i in range(n):
	a = int(input())
	b = input()
	zero = b.count('0')
	one = b.count('1')
	if zero % 2 == 1 and one % 2 == 1:
		print('NO')
	else:
		print('YES')


def palindrome(s):
	a = 0
	b = 0
	for i in s:
		if i == '1':
			a += 1
		elif i == '0':
			b += 1
	if a % 2 == 0 or b % 2 == 0:
		return 'YES'
	return 'NO'
n = int(input())
while n:
	x = int(input())
	s = input()
	print(palindrome(s))
	n = n - 1


T = int(input())
for i in range(T):
	n = int(input())
	m = input()
	x = m.count('0')
	y = m.count('1')
	if x % 2 == 1 and y % 2 == 1:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	s = input()
	zc = 0
	oc = 0
	for i in s:
		if i == '0':
			zc += 1
		else:
			oc += 1
	if zc % 2 and oc % 2:
		print('NO')
	else:
		print('YES')


def can_convert_to_palindrome(s):
	ones = s.count('1')
	zeros = s.count('0')
	if ones % 2 == 0 and zeros % 2 == 0:
		return True
	elif ones % 2 != 0 and zeros % 2 != 0:
		return False
	else:
		return True
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if can_convert_to_palindrome(s):
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	size = int(input())
	s = input()
	one = 0
	zero = 0
	for i in s:
		if i == '1':
			one += 1
		else:
			zero += 1
	if one % 2 == 0 or zero % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	n = int(input())
	bstr = input()
	z_count = bstr.count('0')
	o_count = bstr.count('1')
	if n % 2 == 0:
		if z_count % 2 == 0 and o_count % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')
	t -= 1


n = int(input())
for i in range(n):
	s = int(input())
	d = list(input())
	c = 0
	o = d.count('1')
	if s % 2 == 0:
		if o % 2 == 1:
			c = 1
	if c == 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	string = input()
	if string.count('0') % 2 == 0 or string.count('1') % 2 == 0:
		print('YES')
	else:
		print('NO')


def can_make_palindrome(s):
	odd_count = 0
	freq = [0, 0]
	for c in s:
		freq[int(c)] += 1
	for i in range(2):
		if freq[i] % 2 == 1:
			odd_count += 1
	return odd_count <= 1
t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	if can_make_palindrome(s):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	d = int(input())
	e = input()
	v = e.count('0')
	a = e.count('1')
	if a % 2 == 1 and v % 2 == 1:
		print('NO')
	else:
		print('YES')


goals = int(input())
for distractions in range(goals):
	A = int(input())
	B = input()
	(C, aim) = (0, 0)
	for j in range(A):
		if B[j] == '1':
			C += 1
		else:
			aim += 1
	if A % 2 == 0:
		if C % 2 and aim % 2:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if n % 2 == 0:
		if s.count('0') % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	i = list(map(int, list(input())))
	if n % 2 == 0:
		if sum(i) % 2 == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	s = input()
	zero = s.count('0')
	one = s.count('1')
	if zero % 2 == 0 or one % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	a = input()
	d = {}
	for x in a:
		d.setdefault(x, 0)
		d[x] += 1
	turn = 0
	for y in d.keys():
		if d[y] % 2 != 0:
			if turn == 2:
				exit()
			else:
				turn += 1
	if turn == 2:
		print('NO')
	else:
		print('YES')
	t -= 1