Interview Question: Rearranged Palindrome

A recent software engineer coding interview question I was given was the following:

Check if a given string can be rearranged to form a palindrome. Return true or false.

A palindrome is a sequence of characters that reads the same backwards as it does forwards. So the question is asking if characters in the input string can be rearranged to from a string that reads backwards the same as it does forwards.

I had some difficulty understanding the question at first so here are some example input/outputs to clarify what the question is looking for:

Example:
Input: ‘aabb’
Output: True => ‘baab’

Example:
Input: ‘aaabb’
Output: True => ‘baaab’

Example:
Input: ‘aaabbb’
Output: False

Example:
Input: ‘aabbcc’
Output: True => ‘abccba’

Can you see the pattern? I couldn’t at first. The pattern has to do with the meaning of a palindrome. Since a palindrome can be read the same backwards as forwards, that means the first half of the string is a mirror image of the second half, and vice versa. This is a typical coding question in which knowing the “trick” makes this problem way easier.

The trick is this: Check if there is more than one instance of an odd number of character occurrences .

If there is more than one character that occurs an odd number of times, then the first half of the string would NOT be a mirror image of the second half.

Let’s use the input string of ‘aaabb’ as an example:

How many times does ‘a’ occur? 3 times.

How many times does ‘b’ occur? 2 times.

So, how many characters occur an odd number of times? Just one, since ‘a’ occurs 3 times and 3 is an odd number.

So ‘aaabb’ can be rearranged to form a palindrome because it has at most one odd character occurrence. In order to satisfy the requirements of being a palindrome (mirror image), that character that occurs an odd number of times will be the center of the string.

So, ‘aaabb’ CAN be rearranged to ‘baaab’. Notice the odd occurrence character is smack dab in the center? If there were two or more odd occurrences, one side of the mirror image would be missing a character.

Now, let’s use the input string of ‘aaabbb’ as an example:

How many times does ‘a’ occur? 3 times.

How many times does ‘b’ occur? 3 times.

So, how many characters occur an odd number of times? Two, since ‘a’ occurs 3 times and ‘b’ occurs 3 times. That is two odd occurrences.

So ‘aaabbb’ CANNOT be rearranged into a palindrome because there is no way the first half can mirror the second half knowing there are multiple odd character occurrences.

So you can easily tell if any input string can be rearranged into a palindrome just by counting the number of character occurrences and counting how many odd occurrences there are. To solve this problem in code, all you need is to:

1. Iterate through each character of the input string and build a character map showing the number of occurrences of each character.
2. Iterate through the character map and increment a counter variable if the character occurrence is odd.
3. Check if counter is greater than 1 and return a boolean accordingly.

Here is how I solved it in JavaScript:

Rearranged Palindrome Solution (JavaScript)

That’s it!

Find me on Github:
https://github.com/dougschallmoser