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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/267-palindrome-permutation-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.