267 Palindrome Permutation II

Given a strings, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Givens = "aabb", return["abba", "baab"].

Givens = "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 baseStrand 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