The Problem: Write a function that checks whether any permutation of a string is a palindrome.
Permutation ➡ An ordering of a set of items; in this case the letters of the string.
Palindrome ➡ A 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:
We are looking for permutations of the string.
AND the palindrome does not have to be a real word.
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
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.
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.
.add() , remove values with
.delete(), and check if a value is already present in the set with
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
To test this function, assuming you have
node installed on your machine, open your command line and type
node to launch the node CLI.
Copy and paste our function above into the command line, then pass in various strings to see if any permutations would be a palindrome.
Looks good to me!
We can run interactive ruby from the command line by entering
irb, just like how we did 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.
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?”