Checking if a string is a permutation of a Palindrome

During this post we’ll be writing an algorithm that determines whether a string is a permutation of a Palindrome. We’re not talking about finding out whether a string is a Palindrome, but whether if a string is a permutation of a Palindrome. 

In other words, given a string of scrambled characters, we want to see if it would be possible to rearrange those characters into a word that spells the forward as it does backward (i.e: “oonn” can be re-arranged to form the palindrome “noon”). 

You might be tempted to write code that finds every possible permutation of characters to see if one forms a Palindrome. This would work for small strings but would quickly become time consuming as the amount of possible permutations rises dramatically. And in fact, it’s also not needed. This is likely one such reason why this question (and variations of it) emerge frequently in interview questions and other coding brainteasers — to test the ability for you to take a step back — assess a problem and carefully break it down into its most critical components to produce an efficient and optimized solution.

“Wow”, “Racecar”, “Radar”, “Level”, “Noon” are all examples of palindromes. They each have the following qualities in common: all have an even count of characters, or at most 1 character with an odd # of occurrences. This means that instead of going crazy generating every permutation of a string and checking whether each is a palindrome, we just need to check if the string we start with abides by these rules. 

 

Let’s apply these rules to the string “aacecrr” and see if we can accurately conclude whether the letters in “aacecrr” can be rearranged into a palindrome. We’ll keep count of the # of times we’ve seen each character, along with a count that keeps track of the odd # of characters — incrementing by 1 when any current character count is odd, and decrementing it by 1 when any current character count is even. Below is an illustrated breakdown of what we’ll do as we iterate through each letter in the string (the current character and the counts being decremented/incremented are highlighted in blue):

A A C E C R R

A: 1  (1 is odd so numOdd should be incremented by 1)

numOdd: 1

A A C E C R R

A: 2  (2 is even so numOdd should be decremented by 1)

numOdd: 0

A A C E C R R

A: 2

C: 1 (odd so increment numOdd by 1)

numOdd: 1

A A C E C R R

A: 2

C: 1

E: 1 (odd so increment numOdd by 1)

numOdd: 2

A A C E C R R

A: 2

C: 2 (even so decrement numOdd by 1)

E: 1

numOdd: 1

A A C E C R R

A: 2

C: 2

E: 1

R: 1 (odd so increment numOdd by 1)

numOdd: 2

A A C E C R R

A: 2

C: 2

E: 1

R: 2 (even so decrement numOdd by 1)

numOdd: 1

By the end, numOdd is only 1, as it should be because we only have one unique character, “E”, that has an odd number of occurrences. And since we end with numOdd <= 1, isPermOfPalindrome will return true. You’ll notice with this logic we must scan every character of the string, as even though a character might have an even count at the beginning, it might eventually have an odd count at the end, and vice versa. We just won’t know until the end. 

Now we’re ready to translate this algorithm over to code. I’ve included my java implementation below:

I’m using a HashMap to keep track of the character counts, and just one integer, numOdd, to track the # of unique characters that have an odd frequency. 

Drop any comments or feedback below, and feel free to share your own implementation coded in another language if you have one!