Can a String Become a Palindrome?
National Olympiad — Municipal round (2023 season)
Submission name: palin.cpp
Problem summary
Determine whether each case-sensitive alphanumeric string can be rearranged into a palindrome.
Input
n strings.
Output
One binary answer string preserving input order.
Constraints
0<n<1000; each length<8000.
Worked example
Input and output for the worked example discussed below.
Input
3 abcabc xyz rotor
Output
101
Solution analysis
- Mirrored palindrome positions need equal characters. Only the optional centre can use an unpaired occurrence.
- Count odd character frequencies. A rearrangement exists exactly when this count is at most one, regardless of the original order.
- abcabc has only even counts and can form abccba. xyz has three odd counts and fails; rotor has one and succeeds. Output101.
Why it works
Necessity follows from mirrored pairing. Conversely place half of every character count on the left, mirror it, and put the sole odd remainder in the centre.
Complexity: O(total input length) time and O(1) auxiliary space for fixed ASCII counts.
Watch out. Uppercase and lowercase differ. Even-length palindromes require zero odd counts, not one.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<array>
using namespace std;
// Necessity follows from mirrored pairing.
int main(){
int tests;
cin>>tests;
while(tests--){
string s;
cin>>s;
array<int,128>count{};
for(unsigned char c:s){
count[c]++;
}
int odd=0;
for(int f:count){
odd+=f%2;
}
cout<<(odd<=1?'1':'0');
}
cout<<'\n';
}