Yet Another Palindrome Making Problem Codechef Solution

MAKEPALAGAIN

(100/100) Full Result

Codechef July Lunchtime | AC Code

Chef has a string (containing lowercase Latin letters only) of length where

is even. He can perform the following operation any number of times:

  • Swap and for any

Determine if Chef can convert string to a palindromic string.

Note: A string is called a palindrome if it reads the same backwards and forwards. For example, and are palindromic strings but is not.

Input Format

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

Output Format

For each test case, output YES if Chef can convert the string

to a palindromic string. Otherwise, output NO.

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

Constraints

  • contains lowercase Latin letters only.
  • is even

Sample Input 1

3
6
aabbaa
4
abcd
6
zzxyyx

Sample Output 1

YES
NO
YES

Explanation

Test case

The given string is already a palindrome.

Test case

It can be proven that is it not possible to convert

to a palindromic string.

Test case

We can perform the following operations:

  • Swap and . (Now becomes xzzyyx)
  • Swap and . (Now becomes xyzzyx)
				
					li n;
cin >> n;
string str;
cin >> str;
unordered_map<char, li> mp1;
unordered_map<char, li> mp2;
for (li i = 0; i < n; i++)
{
    if (i == 0 || i % 2 == 0)
    {
        mp1[str[i]]++;
    }
    else
    {
        mp2[str[i]]++;
    }
}
if (mp1 == mp2)
{
    cout << "YES" << endl;
}
else
{
    cout << "NO" << endl;
}
				
			

0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published.