Problem statement

https://leetcode.com/problems/palindrome-permutation-ii/

Solution

First we need to check if we can make palindrome at all. If we can, then create string with its first half and mid if we have odd number of elements. Then we can use problem 0047. Permutations II to gemerate all permutations with repetitions. Or we can use permutations function in python which will generate all $n!$ permutations with repetitions, and then we take only unique ones.

Complexity

It is $O(n!\cdot n)$, where $n$ is equal to s.length//2. Space complexity is the same.

Code

class Solution:
    def generatePalindromes(self, s):
        cnt = Counter(s)
        odds = sum(b%2 == 1 for a,b in cnt.items())
        if odds > 1: return []
        
        half = "".join(t*(cnt[t]//2) for t in cnt)
        mid = ""
        for t in cnt:
            if cnt[t] % 2 == 1: mid = t
        
        ans = set()
        for perm in permutations(half):
            tmp = "".join(perm)
            ans.add(tmp + mid + tmp[::-1])
                
        return ans