LC 0267 [M] Palindrome Permutation II - ALawliet/algorithms GitHub Wiki

we only need to generate the first half of the string

a palindrome can only have 1 odd freq char, and if it does, it is always in the middle: [half][odd char][reversed half]

otherwise all the chars must be even: [half][reversed half]

if there is an odd, we place it in the middle and build the sides. otherwise we just build the sides

class Solution:
    def generatePalindromes(self, s: str) -> List[str]:
        counts = Counter(s)
        odd_char = ''

        # if multiple odd chars, return false
        # sets the single odd char if it exists
        for char in counts:
            if counts[char] % 2 == 1:
                if odd_char:
                    return []
                else:
                    odd_char = char
                    counts[char] -= 1

        def backtrack(cur_perm):
            if len(cur_perm) == len(s) // 2:
                perm = cur_perm + [odd_char] + cur_perm[::-1]
                res.append(''.join(perm))
            else:
                for char in counts:
                    if counts[char] > 0:
                        cur_perm.append(char)
                        counts[char] -= 2
                        backtrack(cur_perm)
                        cur_perm.pop()
                        counts[char] += 2

        res = []
        backtrack([])
        return res