Alice and Bob are playing a game. They have a common string S of length N. The players also have their individual strings A (belonging to Alice) and B (belonging to Bob) which are empty in the beginning. Game begins with Alice and both players take alternate turns.

In her/his turn, the player picks a single character from string S, adds it to the end of their individual string and deletes the picked character from string S.

The game continues until string S is empty. Find whether there exists a sequence of moves such that the strings A and B are same at the end of the game.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the length of the string.
- The next line contains the strings S consisting of lowercase english alphabets.

------ Output Format ------ 

For each test case, output on a new line, YES if there exists a sequence of moves such that the strings A and B are same at the end of the game, and NO otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{5}$
$S$ consists of lowercase english alphabets
- The sum of $N$ over all test cases does not exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
4
abab
5
cbcba
4
abcd
6
pqprqr

----- Sample Output 1 ------ 
YES
NO
NO
YES
----- explanation 1 ------ 
Test case $1$: Consider the following sequence of moves:
- Alice picks the first character of string $S$ and adds it to the end of string $A$. Thus, $S$ becomes bab and $A$ becomes a.
- Bob picks the second character of string $S$ and adds it to the end of string $B$. Thus, the strings are $S =$ bb, $A =$ a, and $B =$ a .
- Alice picks the second character of string $S$ and adds it to the end of string $A$. Thus, the strings are $S =$ b, $A =$ ab, and $B =$ a .
- Bob picks the first character of string $S$ and adds it to the end of string $B$. Thus, $S$ becomes empty, $A =$ ab, and $B =$ ab .

We can see that using this sequence of moves, the final strings $A$ and $B$ are equal.

Test case $2$: There exists no sequence of moves such that the strings $A$ and $B$ become equal in the end.

Test case $3$: There exists no sequence of moves such that the strings $A$ and $B$ become equal in the end.

Test case $4$: Consider the following sequence of moves:
- Alice picks the first character of string $S$ and adds it to the end of string $A$. Thus, $S$ becomes qprqr and $A$ becomes p.
- Bob picks the second character of string $S$ and adds it to the end of string $B$. Thus, the strings are $S =$ qrqr, $A =$ p, and $B =$ p .
- Alice picks the second character of string $S$ and adds it to the end of string $A$. Thus, the strings are $S =$ qqr, $A =$ pr, and $B =$ p .
- Bob picks the third character of string $S$ and adds it to the end of string $B$. Thus, $S$ becomes qq, $A$ becomes pr, and $B$ becomes pr.
- Alice picks the second character of string $S$ and adds it to the end of string $A$. Thus, the strings are $S =$ q, $A =$ prq, and $B =$ pr .
- Bob picks the first character of string $S$ and adds it to the end of string $B$. Thus, $S$ becomes empty, $A =$ prq, and $B =$ prq .

We can see that using this sequence of moves, the final strings $A$ and $B$ are equal.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures


Solutions:
for i in range(int(input())):
	n = int(input())
	l = list(input())
	s = list(set(l))
	a = 0
	for i in range(len(s)):
		b = 0
		for j in range(len(l)):
			if s[i] == l[j]:
				b += 1
		if b % 2 == 0:
			a += 1
	if a == len(s):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	N = int(input())
	STR = input()
	L = []
	for i in range(N):
		L.append(STR[i])
	L1 = set(L)
	L2 = list(L1)
	b = 0
	for i in range(len(L2)):
		if L.count(L2[i]) % 2 == 0:
			b += 1
		else:
			b = 0
			break
	if b != 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	se = set(s)
	flag = 0
	for i in se:
		if s.count(i) % 2 != 0:
			flag = 1
			break
	if flag == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	s = s.lower()
	s = list(s)
	s1 = set(s)
	c = 1
	for i in s1:
		if s.count(i) % 2 != 0:
			c = 0
			break
	if c:
		print('YES')
	else:
		print('NO')
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = list(input())
	s = set(l)
	if n % 2 == 1:
		print('NO')
	else:
		flag = False
		for i in s:
			if l.count(i) % 2 == 1:
				flag = True
				break
		if flag:
			print('NO')
		else:
			print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	my_dict = dict()
	for char in input():
		if char in my_dict:
			my_dict[char] += 1
		else:
			my_dict[char] = 1
	answer = 'YES'
	for (key, val) in my_dict.items():
		if val % 2 == 1:
			answer = 'NO'
			break
	print(answer)


for i in range(int(input())):
	n = int(input())
	s = input()
	k = set(s)
	flag = 1
	for i in k:
		if s.count(i) % 2 != 0:
			flag = 10
	if flag == 10:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s1 = set(s)
	i = 0
	if n % 2 != 0:
		print('NO')
	else:
		l = 0
		for i in s1:
			if s.count(i) % 2 == 0:
				l = l + 1
		if len(s1) == l:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	len = int(input())
	string = input()
	char_count = {}
	for char in string:
		char_count[char] = char_count.get(char, 0) + 1
	all_even = all((count % 2 == 0 for count in char_count.values()))
	print('YES' if all_even else 'NO')


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	if len(s) % 2 != 0:
		print('NO')
	else:
		f = [0] * 26
		c = 0
		for j in s:
			f[ord(j) - 97] = f[ord(j) - 97] + 1
		for g in f:
			if g == 1 or g % 2 != 0:
				c = 1
				break
		if c == 0:
			print('YES')
		else:
			print('NO')


def fun(s, n):
	if n % 2 == 1:
		return 'NO'
	fc = [0] * 27
	for i in s:
		fc[ord(i) % 96] += 1
	for i in s:
		if fc[ord(i) % 96] % 2 == 0:
			continue
		else:
			return 'NO'
	return 'YES'
for i in range(int(input())):
	n = int(input())
	s = input()
	print(fun(s, n))


for t in range(int(input())):
	n = int(input())
	s = input()
	l = []
	if len(s) % 2 != 0:
		print('NO')
	else:
		for i in s:
			if i not in l:
				l.append(i)
			else:
				l.remove(i)
		if len(l) != 0:
			print('NO')
		else:
			print('YES')


for i in range(int(input())):
	n = int(input())
	s = list(str(input()))
	l = [*set(s)]
	x = 0
	for i in l:
		if s.count(i) % 2 != 0:
			x += 1
	if x >= 1:
		print('NO')
	else:
		print('YES')


n = int(input())
for i in range(n):
	n1 = int(input())
	s = input()
	k = set(s)
	count = 0
	for i in k:
		if s.count(i) % 2 != 0:
			count = 1
			break
	if count == 0:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	string = str(input())
	if N % 2 != 0:
		print('NO')
	else:
		stringset = set(string)
		l = len(stringset)
		if N == l:
			print('NO')
		else:
			t = 0
			for i in stringset:
				c = string.count(i)
				if c % 2 == 0:
					t += 1
			if t == l:
				print('YES')
			else:
				print('NO')


n = int(input())
for i in range(n):
	k = int(input())
	k1 = input()
	s = set(k1)
	x = 0
	for i in s:
		if k1.count(i) % 2 == 1:
			x += 1
	if x >= 1:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	arr = list(input())
	a = set(arr)
	x = 0
	for j in a:
		if arr.count(j) % 2 == 1:
			x += 1
	if x >= 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for j in range(t):
	n = int(input())
	s = input()
	d = {}
	for l in s:
		if l in d:
			d[l] += 1
		else:
			d[l] = 1
	c = 0
	for key in d:
		if d[key] % 2 != 0:
			c = 1
	if c == 0:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	x = int(input())
	s = input()
	r = 0
	if len(s) % 2 != 0:
		print('NO')
	else:
		fc = [0] * 26
		for i in s:
			x = ord(i) - 97
			fc[x] += 1
		for i in fc:
			if i % 2 != 0:
				print('NO')
				r = 1
				break
		if r == 0:
			print('YES')


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	l = list(s)
	a = []
	b = []
	while len(l) != 0 and len(a) == len(b):
		a.append(l[0])
		l.remove(l[0])
		for i in range(len(l)):
			if a[len(a) - 1] == l[i]:
				b.append(l[i])
				l.remove(l[i])
				break
	if a == b:
		print('YES')
	else:
		print('NO')


for i in range(0, int(input())):
	n = int(input())
	s = input()
	flag = 0
	list1 = []
	for j in s:
		list1.append(j)
	set1 = set(list1)
	list2 = list(set1)
	for k in list2:
		a = list1.count(k)
		if a % 2 != 0:
			print('NO')
			flag = 0
			break
		else:
			flag = 1
	if flag == 1:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	a = set(s)
	c = 0
	if n % 2 != 0:
		print('NO')
	else:
		for i in a:
			if s.count(i) % 2 != 0:
				c = c + 1
				break
		if c != 0:
			print('NO')
		else:
			print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(input())
	s = list(set(l))
	if n % 2 == 0:
		c = 0
		for i in s:
			if l.count(i) % 2 == 0:
				c = c + 1
		if c == len(s):
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	v = list(s)
	m = set(v)
	o = list(m)
	flag = 0
	for j in o:
		if v.count(j) % 2 == 0:
			flag = 1
		else:
			flag = 0
			print('NO')
			break
	if flag == 1:
		print('YES')


t = int(input())
for x in range(t):
	n = int(input())
	string = list(input())
	set_string = set(string)
	if n % 2 == 1:
		print('NO')
	else:
		c = 0
		for z in set_string:
			if string.count(z) % 2 == 1:
				c = 1
				break
		if c == 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if n % 2 != 0:
		print('NO')
	else:
		a = ''
		b = ''
		f = 0
		for j in s:
			if s.count(j) % 2 == 0:
				s = s.replace(j, '')
			else:
				f = 1
				break
		if f == 1:
			print('NO')
		else:
			print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	dic = {}
	for i in s:
		dic[i] = dic.get(i, 0) + 1
	flag = False
	for i in dic.values():
		if i % 2 != 0:
			flag = True
	if flag:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	s = str(input())
	f = 0
	if n % 2 == 1:
		print('NO')
	else:
		s = list(s)
		x = set(s)
		b = []
		for i in x:
			b.append(s.count(i))
		for i in b:
			if i % 2 != 0:
				f = 1
				break
		if f == 1:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	d = {}
	for i in s:
		if i in d.keys():
			d[i] += 1
		else:
			d[i] = 1
	flag = False
	for i in d.keys():
		if d[i] % 2 != 0:
			flag = True
			break
	if flag:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	L = int(input())
	C = input()
	if len(C) % 2 == 1:
		print('NO')
	else:
		S = set(C)
		for i in S:
			if C.count(i) % 2 == 1:
				print('NO')
				break
		else:
			print('YES')


from collections import Counter

def test():
	n = int(input())
	s = input()
	d = Counter(list(s))
	for i in d.values():
		if i & 1:
			print('NO')
			return
	print('YES')
t = int(input())
for _ in range(t):
	test()


t = int(input(''))
for i in range(t):
	n = int(input(''))
	s = input()
	s1 = set(s)
	x = 0
	for j in s1:
		if s.count(j) % 2 != 0:
			x = 1
			break
	if x == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(0, t, 1):
	n = int(input())
	str = input()
	s = set()
	y = 0
	for char in str:
		if char not in s:
			s.add(char)
			k = str.count(char)
			if k % 2 != 0:
				y = 10
				break
	if y != 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	x = input()
	if n % 2:
		print('NO')
	else:
		xt = set(x)
		if n == len(xt):
			print('NO')
		else:
			t = 0
			for i in xt:
				if x.count(i) % 2:
					print('NO')
					t = 1
					break
			if t == 0:
				print('YES')


for i in range(int(input())):
	n = int(input())
	s = input()
	l = list(s)
	p = []
	for i in set(l):
		if l.count(i) % 2 == 0:
			p.append(1)
		else:
			p.append(0)
	if sum(p) == len(p):
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	A = set(s)
	if len(s) % 2 != 0:
		print('NO')
	else:
		c = 0
		for i in A:
			if s.count(i) % 2 != 0:
				c = 1
				break
			else:
				c = 0
		if c == 1:
			print('NO')
		else:
			print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	l = [x for x in s]
	l2 = []
	for x in list(set(l)):
		if s.count(x) % 2 != 0:
			l2.append(x)
	if len(l2) == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	f = 0
	ml = list(dict.fromkeys(s))
	for i in ml:
		if s.count(i) % 2 != 0:
			f = 1
			break
	if f == 0:
		print('YES')
	else:
		print('NO')


test = int(input())
for i in range(test):
	a = int(input())
	s = input()
	s1 = set(s)
	if a % 2 != 0:
		print('NO')
	else:
		x = 'YES'
		for i in s1:
			if s.count(i) % 2 != 0:
				x = 'NO'
				break
		print(x)


q = int(input())
for i in range(q):
	n = int(input())
	s = input()
	l = [j for j in s]
	s1 = set(l)
	count = 0
	for k in s1:
		if l.count(k) % 2 == 0:
			count += 1
	if count == len(s1):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	s = str(input())
	if n % 2 != 0:
		print('NO')
	else:
		r = set(s)
		flag = True
		for i in r:
			if s.count(i) % 2 != 0:
				flag = False
				break
		if flag:
			print('YES')
		else:
			print('NO')


from collections import Counter
for i in range(int(input())):
	n = int(input())
	e = 0
	d = input()
	b = list(d)
	c = Counter(b)
	for i in c.values():
		if i % 2 == 0:
			e += i
	if e == n:
		print('YES')
	else:
		print('NO')