Palindrome Reorder
Rearrange the letters into a palindrome when possible, otherwise report that no such arrangement exists.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
Rearrange the characters of the given uppercase string so that the result reads the same forward and backward. If no palindrome can be formed, print that clearly.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
A palindrome is controlled by character counts:
every character used in the left half must also appear in the right half
therefore almost every count must be even
at most one character may have an odd count, because only the middle position can stay unmatched
So the algorithm is:
count how many times each character appears
if more than one count is odd, the answer is impossible
otherwise build the left half from \(\lfloor \text{count} / 2 \rfloor\) copies of each letter
put the odd-count character, if it exists, in the middle
mirror the left half to obtain the right half
There is no need for search or backtracking. Once the counts are known, the structure of the palindrome is forced.
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(n + \sigma)\), where \(\sigma\) is the alphabet size
Memory: \(O(\sigma)\)
C++ Solution
The exact repository source used for this solution page.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
std::string s;
std::cin >> s;
std::vector<int> count(26, 0);
for (char c : s) {
++count[c - 'A'];
}
int odd_index = -1;
for (int i = 0; i < 26; ++i) {
if (count[i] % 2 == 1) {
if (odd_index != -1) {
std::cout << "NO SOLUTION\n";
return 0;
}
odd_index = i;
}
}
std::string left_half;
for (int i = 0; i < 26; ++i) {
left_half.append(count[i] / 2, static_cast<char>('A' + i));
}
std::string right_half = left_half;
std::reverse(right_half.begin(), right_half.end());
std::cout << left_half;
if (odd_index != -1) {
std::cout << std::string(count[odd_index] % 2, static_cast<char>('A' + odd_index));
}
std::cout << right_half << '\n';
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
For uppercase English letters, \(\sigma = 26\), so the counting array is tiny.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.