A (1-indexed) string S of length N is said to be anti-palindrome if, for each 1 ≤ i ≤ N, S_{i} \ne S_{(N + 1 - i)}.

You are given a string S of length N (consisting of lowercase Latin letters only). Rearrange the string to convert it into an anti-palindrome or determine that there is no rearrangement which is an anti-palindrome.

If there are multiple rearrangements of the string which are anti-palindromic, print any of them.

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

- The first line of input contains a single integer T — the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N — the length of the string S.
- The second line of each test case contains the string S.

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

For each test case, if it is possible to rearrange S to convert it into an anti-palindrome, print YES in the first line and print the rearranged string in the second line. Otherwise, print NO.

You may print each character of YES and NO in uppercase or lowercase (for e.g. yes, yEs, Yes will be considered identical).

If there are multiple rearrangements of the string which are anti-palindromic, print any of them.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$S$ contains only lowercase Latin letters
- It is guaranteed that the sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
3
abc
8
abccccdd
4
xyyx
6
ppppqr

----- Sample Output 1 ------ 
NO
YES
abddcccc
YES
xxyy
NO

----- explanation 1 ------ 
Test case $1$: No matter how the string is rearranged, the condition $S_{i} \ne S_{(N + 1 - i)}$ will not be satisfied for $i = 2$.

Test case $2$: One possible rearrangement of the string which is anti-palindromic is abddcccc. Other answers, such as ccdaccdb, will also be accepted.

Test case $3$: One possible rearrangement of the string which is anti-palindromic is xxyy.

Test case $4$: It can be shown that none of the rearrangements of $A$ is anti-palindromic.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Constructive algorithms
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	S = input()
	if N % 2 == 0:
		notPossible = False
		alpha = dict()
		for i in S:
			alpha[i] = alpha.get(i, 0) + 1
			if alpha[i] > N / 2:
				notPossible = True
				break
		if notPossible:
			print('NO')
			continue
		sortedAlpha = dict(sorted(alpha.items(), key=lambda item: item[1]))
		finalString = ''
		for (k, v) in sortedAlpha.items():
			finalString += k * v
		halfWayMark = N // 2
		finalString = finalString[:halfWayMark] + finalString[halfWayMark:][::-1]
		print('YES')
		print(finalString)
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	if N % 2 == 1:
		print('NO')
	else:
		S1 = list(S)
		S2 = set(S1)
		D = {}
		for i in S1:
			if i not in D:
				D[i] = 1
			else:
				D[i] += 1
		v = 0
		for i in list(D.values()):
			if i > len(S) / 2:
				print('NO')
				v = 1
				break
		b = sorted(D.items(), key=lambda kv: (kv[1], kv[0]))
		if v == 0:
			print('YES')
			ans = ''
			for i in range(len(b)):
				ans += str(b[i][0]) * b[i][1]
			ans = ans[0:int(len(ans) / 2)] + ans[int(len(ans) / 2):][::-1]
			print(ans)


import math

def check(s, n):
	for i in range(n):
		if s[i] == s[n - i - 1]:
			return False
	else:
		return True

def rotate(s, n):
	l = len(s)
	return s[-n:] + s[:l - n]
t = int(input())
for tc in range(t):
	n = int(input())
	s = list(input())
	if n % 2 != 0:
		print('NO')
		continue
	d = {}
	for i in range(n):
		try:
			d[s[i]] += 1
		except:
			d[s[i]] = 1
	d = {k: v for (k, v) in sorted(d.items(), key=lambda x: x[1])}
	new = ''
	flag = True
	for (k, v) in d.items():
		if v > n // 2:
			flag = False
			break
		new += k * v
	if flag == False:
		print('NO')
		continue
	if check(new, n):
		print('YES')
		print(new)
		continue
	ans = new[:n // 2] + new[n // 2:][::-1]
	if check(ans, n):
		print('YES')
		print(ans)
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	if n % 2 == 1:
		print('NO')
	else:
		d = {}
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		d = dict(sorted(d.items(), key=lambda kv: (kv[1], kv[0])))
		if max(d.values()) > n // 2:
			print('NO')
		else:
			ans = ''
			for i in d:
				ans += i * d[i]
			print('YES')
			final = ans[:n // 2]
			res = ans[n // 2:][::-1]
			print(final + res)