Whiteboarding in Python: Check if a String is a Permutation of a Palindrome

<< Week 2: Queues | Week 4: Binary Search >> | View Solution on GitHub

What you see above is "taco cat" spelled backwards. (Source: popsugar.com)

We're back this week with another practice problem; this time a simpler one involving Arrays and Strings, or, as we call them in Python, Lists and Strings. Let's take a look at the problem:

# Given a string, write a function to check if it is a permutation of a palindrome. 
# A palindrome does not to be limited to just dictionary words. 
# You can ignore casing and non-letter characters.

We have a couple of buzzwords here that they like to use in these sorts of problems. A palindrome you probably know is a word that reads the same backwards and forwards, such as "taco cat". Notice how the space is ignored, and it looks like this problem similarly asks to ignore non-letter characters. A permutation is simply any rearrangement of the letters. For example, we could sort the letters in the string "taco cat" alphabetically to be "aaccott" and it would be a permutation of "tacocat" (We won't sort the string for this solution, but it's good to keep that idea in mind).

Let's start by defining our method. You can follow along on your own in a Repl.it, or write it down the old fashioned way on a whiteboard and piece of paper, and then try type it up and try running it when you're finished. Either way, it's good to try with your own hand.

def check_pali(our_string):
    pass

First things first, the fine print in the prompt says "ignore casing." Okay. So let's call .lower() on our string (which I've conveniently defined as our_string). Remember that .lower() returns the lowercase string, and does not alter the original string, so we'll have to re-save it to our_string.

def check_pali(our_string):
    our_string = our_string.lower()

So let's think about our approach. What properties do all palindromes have in common? Looking at some examples like tacocat, racecar, and kayak, you might notice that each letter appears twice, except for the middle letter. In longer palindromes such as "Do geese see God?", you might notice some letters can show more than twice ('e' appears four times), but at most one letter can appear an odd number of times. So, if we count the number of appearances for each letter, the count has to be even for all letters, and at most one odd count.

We'll create a data structure to store the counts of each letter. The solution in Cracking the Coding Interview implements a Hash Table. What is a Hash Table, you ask? Let's look at the Wikipedia page for Hash Tables:

In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values.

Keys and values? If it sounds like a Python dictionary, you're right, because that's what we're going to use.

We'll initialize the dictionary counts to an empty dictionary.

def check_pali(our_string):
  our_string = our_string.lower()
  counts = {}

Next, let's loop through the string. We'll make a for loop that loops through each character.

for letter in our_string:

Now, we want to make sure we're only counting the letter characters, as non-letters are to be ignored. The simplest, galaxy brain way to do this is to write a string with every letter in the alphabet, and check to see if the character is contained in it:

if letter in "abcdefghijklmnopqrstuvwxyz":

But the other way to do it, which may impress your interviewer, is to use the method ord(), which returns the Unicode value of a given character. You can look up the values for "a" and "z", or try printing them out in the python console with print(ord('a')) and print(ord('z')). Be sure that they are lowercase, since uppercase values are listed first in Unicode. Using these values, the conditional will look like this:

if ord(letter) >= 97 and ord(letter) <= 122:

Now, let's try populating the dictionary with the letter counts. Traditional wisdom is to make a condition where if that key doesn't exist, we initialize it to 1, and if it does, we add one to it. This eliminates the error where we try to access the value at a key that doesn't exist yet. It would look like this:

counts = {}
for letter in our_string:
    if letter in counts.keys():
      counts[letter] += 1
    elif ord(letter) >= 97 and ord(letter) <= 122:
      counts[letter] = 1 

This is perfectly fine. If you want to simplify it a bit further, Python has a built-in class called defaultdict where values can be automatically assumed as integers, meaning that if a new key is called for the first time, its value will be initialized to 0. Then we would just increment each value by one regardless of whether it was already a key in the dictionary. If you're using this method, be sure to include the import at the top of your file.

from collections import defaultdict

counts = defaultdict(int)
for letter in our_string:
    if ord(letter) >= 97 and ord(letter) <= 122:
      counts[letter] += 1 

Cool, so now we should have a dictionary with the count of each letter. If we were to print the dictionary after running the function with something like "Taco cat", we should get something like this:

{'t': 2, 'a': 2, 'c': 2, 'o': 1}

Notice how casing and spaces are ignored.

Next, we'll need to loop through each letter in the dictionary and check that each value is even, with at most one odd value. Remember that a python for loop gives you each key in a dictionary, so we'll save them as the variable letter.

for letter in counts:

Now we want to create a variable to store whether or not we've found one odd value already. We can save it as the variable middle, and then if we see an odd count, we can save it as the middle character. You could also simply set the variable to True or False. Then, to check if a count is odd or even, we use the modulus operator, which returns the remainder after division. % 2 will always return 1 if the value is odd and 0 if even. If there is an odd count and middle already has a "truthy" value, we should return False. Altogether:

middle = ""
for letter in counts:
    if middle and counts[letter] % 2 == 1:
        return False
    elif counts[letter] % 2 == 1:
        middle = letter

Finally, we have to return True if we've looped through the list and everything has checked out. Thus, the statement return True will go outside of the for loop. Here is the final method:

palindrome_permutation.py

def check_pali(our_string):
  our_string = our_string.lower()
  counts = defaultdict(int)
  for letter in our_string:
    if ord(letter) >= 97 and ord(letter) <= 122:
      counts[letter] += 1 
  # print(counts)
  middle = ""
  for letter in counts:
    if middle and counts[letter] % 2 == 1:
      return False
    elif counts[letter] % 2 == 1:
      middle = letter
  return True

If we try running a palindrome like "Taco cat," the method should return True, and something like "something not a palindrome" should return False.

print(check_pali("Taco cat"))
-> True
print(check_pali("Not a palindrome"))
-> False

And that's it. Note that the time complexity of our solution is O(N), since we have to loop through each item in the list at least once.

Bonus: Return a Possible Palindrome

This is an extra "feature" I came up with for this problem. Let's say we are given a string of letters and want to know not only if it is a permutation of a palindrome, but if so, what might the palindrome look like?

Starting with the middle character, we make that the middle of our new palindrome. But what if it appears more than once? We'll have to multiply it by its count. Python makes this easy with string multiplication, where 'a' * 3 returns 'aaa'.

new_pali = ""
if middle:
    new_pali = middle * counts[middle]

Next, we loop through the dictionary and add half of each count to either side of the middle character. Division returns a decimal number, otherwise known as a float. Therefore, to be able to do string multiplication, we have to recast it to an int. Be sure to comment out the line where we returned True earlier.

  new_pali = ""
  if middle:
    new_pali = middle * counts[middle]
  for letter in counts:
    if letter != middle:
      new_pali = letter * int(counts[letter] / 2) + new_pali + letter * int(counts[letter] / 2) 
  return new_pali

Printing the result of "Taco cat" will return "catotac". Neat! And if you pass in any word twice, it will make it into a palindrome. For example, "word word" returns "drowword". I know this method was the one thing missing in your life. You're welcome.

Thanks for tuning in this week. We'll return next Monday to start learning algorithms. See you then!

<< Week 2: Queues | Week 4: Binary Search >> | View Solution on GitHub

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly Seattle. This blog is not associated with GA.