# 267 Palindrome Permutation II

Given a string`s`, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
For example:
Given`s = "aabb"`, return`["abba", "baab"]`.
Given`s = "abc"`, return`[]`.
The Idea: This algorithm take ideas from two different concepts and combines them. First: how can we accurately define what is palindromic? A palindrome has some `[baseStr] + [midElement] + [reverse(baseStr)]`. Note that both `baseStr`and `midElement` can be the empty string, so this definition follows true for both even and odd length strings. We can identify these components by counting the occurrences of `s` into a hash table. There can only be ever a single instance (at most) of an odd frequency (from which 1 it's elements has to be within the center of the string), otherwise s can not be a palindrome. There can be 0 or more instances of an even frequency.
Second: once these components are identified, we can then generate all the permutations of `baseStr`, and append to a solution vector for `[baseStr] + [midElement] + [reverse(baseStr)]`
Complexity: O(n!) time and O(|unique(s)|) extra space
from collections import Counter
class Solution:
def permuteUnique(self, iterable):
sol = ['']
for it in iterable:
next_sol = []
for prev in sol:
for i in range(0, len(prev) + 1):
next_sol.append(prev[:i] + it + prev[i:])
if i < len(prev) and prev[i] == it:
break
sol = next_sol
return sol
def generatePalindromes(self, s):
"""
:type s: str
:rtype: List[str]
"""
c = Counter(s)
mid, base = '', ''
for char, freq in c.items():
if freq % 2 == 1 and mid:
return []
elif freq % 2 == 1:
mid = char
if freq > 1:
base += char * (freq // 2)
else:
base += char * (freq // 2)
all_perms = self.permuteUnique(base)
palindrome = []
for base_perm in all_perms:
palindrome.append(base_perm+mid+base_perm[::-1])
return palindrome