# 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

```python
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
```