Anti Palindrome solution codechef- A (11-indexed) string SS of length NN is said to be anti-palindrome if, for each 1≤i≤N1≤i≤N, Si≠S(N+1−i)Si≠S(N+1−i). You are given a string SS of length NN (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.

Anti Palindrome solution codechef

A (11-indexed) string SS of length NN is said to be anti-palindrome if, for each 1iN1≤i≤NSiS(N+1i)Si≠S(N+1−i).

You are given a string SS of length NN (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 Anti Palindrome solution codechef

  • The first line of input contains a single integer TT — the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains an integer NN — the length of the string SS.
  • The second line of each test case contains the string SS.

Output Format

For each test case, if it is possible to rearrange SS 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. yesyEsYes will be considered identical).

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

Constraints

  • 1T1041≤T≤104
  • 1N1051≤N≤105
  • SS contains only lowercase Latin letters
  • It is guaranteed that the sum of NN over all test cases does not exceed 21052⋅105.

Sample Input 1  Anti Palindrome solution codechef

4
3
abc
8
abccccdd
4
xyyx
6
ppppqr

Sample Output 1 

NO
YES
abddcccc
YES
xxyy
NO

Explanation Anti Palindrome solution codechef

Test case 11: No matter how the string is rearranged, the condition SiS(N+1i)Si≠S(N+1−i) will not be satisfied for i=2i=2.

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

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

Test case 44: It can be shown that none of the rearrangements of AA is anti-palindromic.

Leave a Comment

Your email address will not be published.