Question

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

Example 1:

Input: "aabb"
Output: ["abba", "baab"]

Example 2:

Input: "abc"
Output: []

Solution

class Solution(object):
    def generatePalindromes(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if len(s) <= 1:
            return [s]

        charCount = dict()
        for c in s:
            if c in charCount:
                charCount[c] += 1
            else:
                charCount[c] = 1

        odd = len(s) % 2 == 1
        mid = ""

        for c, co in charCount.items():
            if co % 2 == 1:
                if odd:
                    if co > 1:
                        charCount[c] = co // 2
                    else:
                        del charCount[c]
                    mid = c
                    odd = False
                else:
                    return []
            else:
                charCount[c] = co // 2

        permutations = list()
        self.__permutations(permutations, charCount, [])
        return [p + mid + p[::-1] for p in permutations]

    def __permutations(self, res, count, partial):
        if len(count) == 0:
            res.extend(partial)
            return
        for c in count:
            new_partial = list() if len(partial) > 0 else c
            if count[c] == 1:
                del count[c]
            else:
                count[c] -= 1
            for p in partial:
                new_partial.append(p + c)
            self.__permutations(res, count, new_partial)
            if c not in count:
                count[c] = 1
            else:
                count[c] += 1