# Can anyone plz explain how he achieved it

You are given a string S containing only lowercase characters. You can rearrange the string and you have to print minimum number of characters needed(can be 0) to make it palindrome.

### Sample Input:

``````3
1
a
9
abbbcbddd
6
abcdef
``````

### Sample Output:

`````` 0
2
5
``````

#include <bits/stdc++.h>
using namespace std;

int main(){
int t{};
cin>>t;
while(t–){
int n{};
cin >> n;
char a[n];
int count[26]{},odds{};
for (int i = 0; i < n;i++){
cin >> a[i];
count[(int)a[i] - 97]++;
}
for (int i = 0; i < 26;i++){
if(count[i]%2!=0){
odds++;
}
}
if(odds>=1){
cout << odds - 1 << endl;
}
else{
cout << 0 << endl;
}

``````}
``````

}

The solution is fairly basic. The approach is as follows.

• Store the frequency of each character in an Array.
• Now, to make any String Palindrome by rearranging the Characters, it is enough if one of the two conditions are satisfied.
2. All characters have Even Frequency except one Character (Odd Frequency).
Ex: aabcc <----> acbca

So, what is the solution now?
If all characters have Even Frequency, ans = 0.
else, ans = (number of characters having odd Frequency) - 1
(Since, we need to minimise the number of operations, we leave one of the characters with odd frequency undisturbed).

1 Like

I don’t understand why I’m getting a WA when I’m using that exact same logic: Solution: 41451639 | CodeChef

1 Like

Extra whitespace in the test input (e.g. after a string) would cause your solution to give the wrong answer - this seems to be bewilderingly common with third-party contests.

Edit:

To answer the inevitable question: no, I never get tired of being right XD

3 Likes

Omg yeah you were right. It gave me AC when I added `.strip()`. Also, the BOSON problem, nobody has gotten AC with Python 3.6. I saw another solution in C++ get it right using the same logic as me.

1 Like