[Solution] Yet Another Palindrome Making Problem solution codechef

Yet Another Palindrome Making Problem solution codechef – Chef has a string AA (containing lowercase Latin letters only) of length NN where NN is even. He can perform the following operation any number of times:

  • Swap AiAi and Ai+2Ai+2 for any 1i(N2)1≤i≤(N−2)

Table of Contents

[Solution] Yet Another Palindrome Making Problem solution codechef

Determine if Chef can convert string AA to a palindromic string.

Note: A string is called a palindrome if it reads the same backwards and forwards. For example, 𝚗𝚘𝚘𝚗noon and 𝚕𝚎𝚟𝚎𝚕level are palindromic strings but 𝚎𝚋𝚋ebb is not.

Input Format

  • The first line contains a single integer TT — the number of test cases. Then the test cases follow.
  • The first line of each test case contains an integer NN — the length of the string AA.
  • The second line of each test case contains a string AA of length NN containing lowercase Latin letters only.

Output Format

For each test case, output YES if Chef can convert the string AA to a palindromic string. Otherwise, output NO.

You may print each character of YES and NO in either uppercase or lowercase (for example, yesyEsYes will be considered identical).

[Solution] Yet Another Palindrome Making Problem solution codechef

  • 1T2001≤T≤200
  • 1N10001≤N≤1000
  • SS contains lowercase Latin letters only.
  • NN is even

Sample Input 1 

3
6
aabbaa
4
abcd
6
zzxyyx

Sample Output 1 

YES
NO
YES

[Solution] Yet Another Palindrome Making Problem solution codechef Explanation

Test case 11: The given string is already a palindrome.

Test case 22: It can be proven that is it not possible to convert AA to a palindromic string.

Test case 33: We can perform the following operations:

  • Swap A1A1 and A3A3. (Now AA becomes xzzyyx)
  • Swap A2A2 and A4A4. (Now AA becomes xyzzyx)

For Solution

Click Here

Leave a Comment