Palindrome Permutations

This was kind of a weird problem, but the solution was kind of fun to write. Given a string, determine if it’s a palindrome and then write out all the possible permutations of palindromes that string potentially would have.

Here’s my solution:

import collections
import itertools

def palinpermute(s):
    s = s.replace(" ", "")
    c = collections.Counter(s)

    pivot = ''
    for k, v in c.iteritems():
        if v % 2 != 0:
            if not pivot:
                pivot = k
            else:
                return (False, [])

    newStr = ""
    for k, v in c.iteritems():
        if k != pivot:
            newStr += k*(v/2)

    palins = list()
    for c in itertools.permutations(newStr):
        palins.append("".join(c) + pivot + "".join(reversed(c)))

    return (True, palins)

Like a lot of the other solutions to string problems, we’re back to using the Counter again. In this case we use it to make certain that for each character, there has to be a matching one. If there isn’t a matching one, choose that character as a pivot point for our palindrome. Once we’ve selected a pivot point, there can’t be another one, so just return False and an empty list if we find one.

This next part is probably not obvious:

    newStr = ""
    for k, v in c.iteritems():
        if k != pivot:
            newStr += k*(v/2)

This generates a half of a palindrome which we’re going to use to find all of the permutations. If we had the palindrome tacocat, we would end up with a string like act here. When we call itertools.permutations(), that’s going to come up with a list which looks like [('a', 'c', 't'), ('a', 'c', 't'), ('c', 'a', 't'), ('t', 'a', 'c'), ('c', 't', 'a'), ('t', 'c', 'a')]. Now it’s just a simple matter of joining each of these lists into new strings around our pivot point (if we have one), and we’ve found each of the potential palindromes.

The runtime complexity here comes down to how itertools.permutations() works. The permutations come out in lexigraphical sort order, so that’s at least n*log(n) average. Behind the scenes it’s doing something more akin to itertools.product() and filtering out repeated results, which means this can get kind of ugly really quickly from a performance standpoint.

I’m sure there are some interviewers out there who might think using itertools.permutations() feels like cheating. My take on it when I have interviewed candidates is that with very few exceptions it’s fair game to use parts of any standard library for any given programming language. Regardless, it’s not that hard to write some kind of recursive function which generates the same list if the interviewer is demanding it.