Anti Palindrome solution codechef

Anti Palindrome solution codechef

A string  is called semi-palindrome if you can rearrange the characters of  to make it into a palindrome.
For eg. if �=����, it isn’t a palindrome as of now, but it can be rearranged to form ����, which is a palindrome. Thus, �=���� is a semi-palindrome.

An anti-palindrome is the opposite of a semi-palindrome. In particular, a string  is called an anti-palindrome if it is not possible to rearrange the characters of  to make it into a palindrome.
For eg. if �=���, there is no rearrangement of this string which makes it into a palindrome. Hence, �=��� is an anti-palindrome.

Now on to the problem:

You are given a string �=�1�2…�� consisting of  english lowercase letters.

Your aim is to convert  into an anti-palindrome. For this, you are allowed to do the following operation as many times as you want (even 0 times) :

• Select an index  (1≤�≤�) and change �� to any other english lowercase letter.

Find the minimum number of operations needed to make  into an anti-palindrome.

Note: It can be proven that for the given constraints (2≤�≤105), it is always possible to make  into an anti-palindrome using the operations.

Anti Palindrome solution codechef

• The first line of input will contain a single integer , denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains an integer  — the length of the string .
• The next line contains the string  of length .

Output Format

For each test case, output the minimum number of operations needed to make  into an anti-palindrome.

Constraints

• 1≤�≤5⋅105
• 2≤�≤105
•  contains only english lowercase letters.
• The sum of  over all testcases won’t exceed 105.

Sample 1:

Input

Output

5
2
ab
2
aa
3
abc
3
aaa
3
abb

0
1
0
2
1


Explanation:

Testcase 1: The given string �� is already an anti-palindrome, since there is no way to rearrange the letters to make it into a palindrome. So, we don’t need to do any operations on it to make it an anti-palindrome. Hence the answer is 0.

Testcase 2: The given string �� is a palindrome, and so it is not an anti-palindrome. We can change it to �� using 1 operation, and it becomes an anti-palindrome. Hence the answer is 1.

Testcase 3: The given string ��� is already an anti-palindrome, since there is no way to rearrange the letters to make it into a palindrome. So, we don’t need to do any operations on it to make it an anti-palindrome. Hence the answer is 0.

Testcase 4: The given string ��� is a palindrome, and so it is not an anti-palindrome. We can change it to ��� using 2 operations, and it becomes an anti-palindrome. There is no way to make it into an anti-palindrome using only 1 operation. Hence the answer is 2.

Testcase 5: The given string ��� is a semi-palindrome, since it can be rearranged to form ��� which is a palindrome. So ��� is not an anti-palindrome. We can change it to ��� using 1 operation, and it becomes an anti-palindrome. Hence the answer is 1.