# 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:

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

Here is how I solved it in JavaScript:

That’s it!

Find me on Github:

https://github.com/dougschallmoser