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.
  1. All characters have Even Frequency. Ex: acabaadbcd <----> cdabaabadc.
  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