# LeetCode 267: Palindrome Permutation II

## Problem Restatement

We are given a string `s`.

Return all palindromic permutations of `s` without duplicates.

A palindrome reads the same forward and backward.

If no palindromic permutation exists, return an empty list.

The answer may be returned in any order. The constraints are `1 <= s.length <= 16`, and `s` contains only lowercase English letters.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A lowercase string `s` |
| Output | List of unique palindromic permutations |
| Duplicate rule | Do not return duplicate strings |
| Invalid case | Return `[]` if no palindrome can be formed |

Example function shape:

```python
def generatePalindromes(s: str) -> list[str]:
    ...
```

## Examples

Example 1:

```python
s = "aabb"
```

Valid palindromic permutations are:

```python
"abba"
"baab"
```

Answer:

```python
["abba", "baab"]
```

Example 2:

```python
s = "abc"
```

Each character appears once.

There are three odd-count characters, so no palindrome can be formed.

Answer:

```python
[]
```

Example 3:

```python
s = "aaa"
```

The only palindromic permutation is:

```python
"aaa"
```

Answer:

```python
["aaa"]
```

## First Thought: Generate Every Permutation

A direct method is:

1. Generate every unique permutation of `s`.
2. Check whether each permutation is a palindrome.
3. Keep the valid ones.

This works for very small strings, but it wastes most of the work.

For example, `"aabb"` has several permutations, but only two are palindromes.

## Problem With Brute Force

Generating all permutations can take factorial time.

For a string of length `n`, there can be up to:

```python
n!
```

permutations.

But a palindrome is fully determined by its left half, middle character, and mirrored right half.

So we should generate only the left half.

## Key Insight

A palindrome can have at most one character with an odd count.

For example:

```python
"aabb"
```

has counts:

| Character | Count |
|---|---:|
| `a` | 2 |
| `b` | 2 |

There is no odd-count character.

The palindrome half contains:

```python
"ab"
```

Permutations of the half are:

```python
"ab"
"ba"
```

Mirror each one:

```python
"ab" + "" + "ba" = "abba"
"ba" + "" + "ab" = "baab"
```

For:

```python
"aaa"
```

counts are:

| Character | Count |
|---|---:|
| `a` | 3 |

The middle character is:

```python
"a"
```

The half contains:

```python
"a"
```

So the result is:

```python
"a" + "a" + "a" = "aaa"
```

## Algorithm

1. Count character frequencies.
2. If more than one character has an odd count, return `[]`.
3. Build:
   - `mid`: the one odd-count character, or empty string.
   - `half`: each character repeated `count // 2` times.
4. Sort `half`.
5. Backtrack to generate all unique permutations of `half`.
6. For each half permutation `left`, build:
   ```python id="u9r364"
   left + mid + left[::-1]
   ```
7. Return all generated palindromes.

## Walkthrough

Use:

```python
s = "aabb"
```

Counts:

```python
a -> 2
b -> 2
```

No middle character.

Build half:

```python
half = ["a", "b"]
mid = ""
```

Backtracking generates:

```python
left = "ab"
left = "ba"
```

Build palindromes:

```python
"ab" + "" + "ba" = "abba"
"ba" + "" + "ab" = "baab"
```

Return:

```python
["abba", "baab"]
```

Now use:

```python
s = "abc"
```

Counts:

```python
a -> 1
b -> 1
c -> 1
```

There are three odd counts.

Return:

```python
[]
```

## Correctness

A palindrome mirrors its left half onto its right half. Therefore each character must appear in pairs, except possibly one character placed in the center.

The algorithm first checks this necessary condition by counting odd frequencies. If more than one odd frequency exists, no palindrome can be formed, so returning an empty list is correct.

If zero or one odd frequency exists, every palindrome permutation is determined by choosing an ordering of the half characters. The right half is then forced to be the reverse of the left half, and the middle character is fixed when it exists.

The algorithm generates every unique permutation of the half string. For each generated half, it constructs exactly one palindrome. Since duplicate half permutations are skipped, duplicate palindromes are not produced.

Every valid palindrome corresponds to exactly one ordering of the half characters. Therefore the algorithm returns all and only valid palindromic permutations.

## Complexity

Let `m = len(s) // 2`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(P * n)` | `P` half-permutations are generated, and each output string has length `n` |
| Space | `O(m)` | Backtracking path and used array, excluding output |

If all half characters are distinct, then:

```python
P = m!
```

Repeated characters reduce the number of unique permutations.

## Implementation

```python
from collections import Counter
from typing import List

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

        odd_chars = [ch for ch, freq in count.items() if freq % 2 == 1]

        if len(odd_chars) > 1:
            return []

        mid = odd_chars[0] if odd_chars else ""

        half = []
        for ch, freq in count.items():
            half.extend([ch] * (freq // 2))

        half.sort()

        ans = []
        used = [False] * len(half)
        path = []

        def backtrack() -> None:
            if len(path) == len(half):
                left = "".join(path)
                ans.append(left + mid + left[::-1])
                return

            for i in range(len(half)):
                if used[i]:
                    continue

                if i > 0 and half[i] == half[i - 1] and not used[i - 1]:
                    continue

                used[i] = True
                path.append(half[i])

                backtrack()

                path.pop()
                used[i] = False

        backtrack()
        return ans
```

## Code Explanation

We count all characters:

```python
count = Counter(s)
```

Then find odd-count characters:

```python
odd_chars = [ch for ch, freq in count.items() if freq % 2 == 1]
```

If there is more than one, a palindrome cannot be formed:

```python
if len(odd_chars) > 1:
    return []
```

The middle character is the only odd-count character, if it exists:

```python
mid = odd_chars[0] if odd_chars else ""
```

The half list stores half of every character count:

```python
half.extend([ch] * (freq // 2))
```

Sorting helps skip duplicate permutations cleanly:

```python
half.sort()
```

The duplicate skip rule is:

```python
if i > 0 and half[i] == half[i - 1] and not used[i - 1]:
    continue
```

This prevents generating the same half permutation multiple times.

When a full half is built:

```python
left = "".join(path)
ans.append(left + mid + left[::-1])
```

we mirror it around the middle to form a palindrome.

## Testing

```python
def normalize(xs: list[str]) -> list[str]:
    return sorted(xs)

def run_tests():
    s = Solution()

    assert normalize(s.generatePalindromes("aabb")) == normalize(["abba", "baab"])
    assert normalize(s.generatePalindromes("abc")) == []
    assert normalize(s.generatePalindromes("aaa")) == ["aaa"]
    assert normalize(s.generatePalindromes("a")) == ["a"]
    assert normalize(s.generatePalindromes("aa")) == ["aa"]
    assert normalize(s.generatePalindromes("aabbc")) == normalize(["abcba", "bacab"])
    assert normalize(s.generatePalindromes("aaaa")) == ["aaaa"]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"aabb"` | Standard two-answer case |
| `"abc"` | More than one odd count |
| `"aaa"` | Odd length with one middle |
| `"a"` | Single-character palindrome |
| `"aa"` | Even-length single result |
| `"aabbc"` | Odd middle with multiple half permutations |
| `"aaaa"` | Duplicate-heavy input |