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