Can these letters be rearranged into a palindrome?

Question

Given a string, decide whether its characters can be reordered into a palindrome. You are free to permute the letters any way you like.

"carerac"  -> True    # e.g. "racecar"
"aabb"     -> True    # e.g. "abba"
"abc"      -> False

Return a boolean in $O(n)$ time. You do not need to produce the palindrome, only decide if one exists.

Accepted Answer

A palindrome mirrors around its center. Every character except possibly one middle character must appear an even number of times, since each occurrence on the left half is matched by one on the right half. A middle character (present only when the length is odd) is the single exception, so it may have an odd count. Therefore a rearrangement into a palindrome exists exactly when at most one character has an odd frequency. Tracing "carerac": the counts are c:2, a:2, r:2, e:1, so exactly one character (e) is odd, odd = 1 <= 1, return True (it rearranges to "racecar"). For "abc" all three counts …

Can these letters be rearranged into a palindrome?

Your answer

More Coding questions