Palindrome Permutations

avatar
Marshal Murphy
May 29, 2020 - 3 MIN READ

The Problem: Write a function that checks whether any permutation of a string is a palindrome.

palindrome permutations

PermutationAn ordering of a set of items; in this case the letters of the string.

PalindromeA word that is spelled the same way forwards as it is backwards.


Said another way, are there any combinations of the letters in a given string that could be a palindrome?

Let’s explore a couple of examples to help better define what this problem is asking:

  • racecar = true
  • rcaerca = true
  • racecap = false
  • rcaepca = false

We are looking for permutations of the string.

AND the palindrome does not have to be a real word.


Approach

The brute force approach would be to write a function that evaluated every permutation of the string and checked if it were a palindrome.

However, this approach would be inefficient and resource consuming. Is there a better way?

What do we know about palindromes?

For a string to be spelled the same way both forwards and backwards, it must have an even number of each character…

… with the exception being for strings of an uneven length, like racecar, which has that centre e.

Therefore, each letter in the string must occur an even number of times, with only one letter permitted to occur an odd number of times.

Now we can evaluate the string and count both odd and even letters

But when it comes down to it, do we really care how often a character appears an even number of times?

We expect all characters to appear an even number of times, except for possible one.

So let’s write a function that takes in a string and checks if a character appears an odd number of times. If > 1 characters appear an odd number of times, it cannot be a palindrome.


Sets

There are a number of ways to keep track of odd quantities of letters, but here I am opting to use a Set (or hash).

A Set object is a collection of unique values.

In JavaScript, we can add values to this set with .add() , remove values with .delete(), and check if a value is already present in the set with .has().

By using a set for this problem, we can iterate over the string’s characters, adding them to the set object if they are not already present in it, and removing them if they are.

This will ultimately leave us with only the characters that appear an odd number of times.

We can then determine if a palindrome is possible when the .size of the set is <= 1.


We should have enough now to solve this problem. Let’s try writing solutions in JavaScript and Ruby, and then we’ll test them out.

JavaScript

To test this function, assuming you have node installed on your machine, open your command line and type node to launch the node CLI.

> node

Copy and paste our function above into the command line, then pass in various strings to see if any permutations would be a palindrome.

javascript test

Looks good to me!


Ruby

We can run interactive ruby from the command line by entering irb, just like how we did with node.

> irb

With irb , you probably won’t need to specify require 'set' in the command line.

Paste in the above function and pass in various strings to determine if any contain permutations that would be a palindrome.

ruby test


Learnings

The main thing we learned here is an effective way to use Sets.

A set uses a hash-table as it’s underlying data structure.

So, if you ever approach a problem that looks like it needs brute force, ask yourself: “Can I do this better with a set or hash?

Marshal Murphy 2020