# 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.