LeetCode 267: Palindrome Permutation II Solution in Python – A Step-by-Step Guide

What Is LeetCode 267: Palindrome Permutation II?

In LeetCode 267: Palindrome Permutation II, you’re given a string s, and your goal is to return a list of all unique palindromic permutations—strings that read the same forward and backward—assuming the string can form at least one palindrome. A palindrome permutation requires at most one character with an odd count (the middle), with all others having even counts. This problem builds on LeetCode 266: Palindrome Permutation, moving from checking feasibility to generating all possibilities.

Problem Statement

• Input: A string s.
• Output: A list of strings—all unique palindromic permutations.
• Rules: Permutations must be palindromes; return empty list if no palindrome is possible; order doesn’t matter.

Constraints

• s.length: 1 to 16.
• s contains only lowercase English letters.

Examples

• Input: s = "aab"
• Output: ["aba", "baa"] (both are palindromes).
• Input: s = "aabb"
• Output: ["aabb", "abba", "baab", "bbaa"] (all unique palindromes).
• Input: s = "abc"
• Output: [] (no palindrome possible—three odd counts).

Understanding the Problem: Crafting Palindromes

To solve LeetCode 267: Palindrome Permutation II in Python, we need to generate all unique permutations of a string that form palindromes. A palindrome looks like a mirror: the left half matches the right half reversed, with an optional single character in the middle if the length is odd. For "aab" (a:2, b:1), we can make "aba" or "baa"—both work because 'a' pairs up, and 'b' sits in the middle. A basic way—generating all permutations and filtering palindromes—works but is slow and wasteful. We’ll use two methods: 1. Best Solution (Backtracking with Frequency): O(k * 2^k) time—fast and targeted (k is unique characters). 2. Alternative Solution (Recursive Permutation with Filtering): O(n!) time—clear but inefficient.

Let’s dive into the best solution with a friendly, detailed walkthrough.

Best Solution: Backtracking with Character Frequency

Why This Is the Best Solution

The backtracking approach with character frequency is the top pick for LeetCode 267 because it runs efficiently—focusing only on palindrome possibilities—and avoids generating invalid permutations. By counting character frequencies first and building half the palindrome, it cuts down the work to O(k * 2^k) time (where k is the number of unique characters), making it both quick and smart.

How It Works

Think of this solution as building a palindrome like a sandwich: you start with the middle (if there’s an odd character), then add matching bread slices (pairs of even-count characters) on both sides, trying every way to arrange them. Here’s how it works, step-by-step, explained simply:

• Step 1: Count Characters:
• Make a dictionary to count how many times each letter appears in the string.
• For "aabb": {a:2, b:2}.
• Step 2: Check Feasibility:
• A palindrome needs at most one character with an odd count (the middle).
• Count odd occurrences: if more than 1, return []—no palindrome possible.
• "aabb": 0 odds (ok), "abc": 3 odds (not ok).
• Step 3: Split Even and Odd:
• For each character:
• Even count → Use half in the left side (e.g., "aa" → "a").
• Odd count → Use (count-1)/2 in the left, put the extra in the middle (e.g., "aaa" → "a" left, "a" middle).
• "aab": {a:2, b:1} → Left: "a", Middle: "b".
• Step 4: Build Half with Backtracking:
• Use the even halves to build the left side, trying all combinations.
• For "aabb": Half = "ab", permutations: "ab", "ba".
• Step 5: Mirror to Make Palindromes:
• For each left half, add the middle (if any) and the reversed left half.
• "aab": "a" + "b" + "a" = "aba", "b" + "a" + "a" = "baa".
• Step 6: Collect Results:
• Store all unique palindromes in a list.

It’s like assembling a mirrored picture—arrange one side, flip it, and stick the middle in between!

Step-by-Step Example

Example: s = "aab"

• Step 1: Count: {a:2, b:1}.
• Step 2: Odds = 1 (b), feasible.
• Step 3:
• Half: a:2 → "a", b:1 → "" (middle = "b").
• Left half chars: "a".
• Step 4: Permute "a": ["a"] (only one char).
• Step 5: Build:
• "a" + "b" + "a" = "aba".
• Swap (already unique): "baa".
• Step 6: Result: ["aba", "baa"].

Example: s = "aabb"

• Step 1: {a:2, b:2}.
• Step 2: Odds = 0, feasible.
• Step 3: Half: "a", "b", no middle.
• Step 4: Permute "ab": ["ab", "ba"].
• Step 5:
• "ab" + "" + "ba" = "abba".
• "ba" + "" + "ab" = "baab".
• Step 6: Result: ["abba", "baab"] (others like "aabb" emerge with full perm).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

Copy codeclass Solution:
    def generatePalindromes(self, s: str) -> List[str]:
        # Step 1: Count character frequencies
        count = {}
        for char in s:
            count[char] = count.get(char, 0) + 1

        # Step 2: Check if palindrome is possible
        odd_count = sum(1 for c in count.values() if c % 2 == 1)
        if odd_count > 1:
            return []  # More than one odd means no palindrome

        # Step 3: Split into half and middle
        half = []
        middle = ""
        for char, freq in count.items():
            half.extend([char] * (freq // 2))  # Add half the evens
            if freq % 2 == 1:
                middle = char  # Odd char goes in middle

        # Step 4: Backtrack to generate left halves
        result = []
        def backtrack(curr, used):
            if len(curr) == len(half):
                # Build full palindrome
                palindrome = "".join(curr) + middle + "".join(curr[::-1])
                result.append(palindrome)
                return
            for i in range(len(half)):
                if not used[i] and (i == 0 or half[i] != half[i-1] or used[i-1]):
                    used[i] = True
                    curr.append(half[i])
                    backtrack(curr, used)
                    curr.pop()
                    used[i] = False

        # Step 5: Start backtracking
        backtrack([], [False] * len(half))
        return result

• Line 3-6: Build a dictionary counting each character.
• Line 8-10: Count odd frequencies; if more than 1, no palindrome possible.
• Line 12-17: Split into half (even counts divided by 2) and middle (odd char).
• Line 19-31: Backtrack to permute the left half:
• Base case: Full half length, build palindrome.
• Loop: Try each unused char, skip duplicates unless previous is used.
• Line 33: Start with empty current and unused flags.
• Time Complexity: O(k * 2^k)—where k is unique chars, exponential but small.
• Space Complexity: O(n)—result list and recursion stack.

This solution is like a palindrome chef—cook half, mirror it, and serve!

Alternative Solution: Recursive Permutation with Filtering

Why an Alternative Approach?

The recursive permutation method generates all possible permutations of the string, then filters out the non-palindromes. It’s slower (O(n!)) but shows the full range of possibilities, making it a great way to explore the problem before optimizing.

How It Works

Think of this as shuffling a deck of cards every way possible, then picking out the ones that spell the same backward and forward. Here’s how it works, step-by-step:

• Step 1: Generate all permutations recursively.
• Step 2: Check each for palindrome property.
• Step 3: Store unique ones in a set.

It’s like trying every outfit combo—see what fits the mirror test!

Step-by-Step Example

Example: s = "aab"

• Step 1: Permutations: "aab", "aba", "baa".
• Step 2: Check:
• "aab": No.
• "aba": Yes.
• "baa": Yes.
• Step 3: Result: ["aba", "baa"].

Code for Recursive Approach

Copy codeclass Solution:
    def generatePalindromes(self, s: str) -> List[str]:
        # Step 1: Check feasibility
        count = {}
        for char in s:
            count[char] = count.get(char, 0) + 1
        odd_count = sum(1 for c in count.values() if c % 2 == 1)
        if odd_count > 1:
            return []

        # Step 2: Generate permutations
        def permute(chars, curr, used, result):
            if len(curr) == len(chars):
                perm = "".join(curr)
                if perm == perm[::-1]:
                    result.add(perm)
                return
            for i in range(len(chars)):
                if not used[i] and (i == 0 or chars[i] != chars[i-1] or used[i-1]):
                    used[i] = True
                    curr.append(chars[i])
                    permute(chars, curr, used, result)
                    curr.pop()
                    used[i] = False

        # Step 3: Run and return
        chars = list(s)
        result = set()
        permute(chars, [], [False] * len(chars), result)
        return list(result)

• Time Complexity: O(n!)—all permutations.
• Space Complexity: O(n!)—storing permutations.

It’s a full sweep but heavy.

Comparing the Two Solutions

• Best Solution (Backtracking):
• Pros: O(k * 2^k) time, efficient, targeted.
• Cons: Backtracking might feel intricate.
• Alternative Solution (Recursive):
• Pros: O(n!) time, shows all perms.
• Cons: Slow, space-heavy.

Backtracking wins for speed.

Additional Examples and Edge Cases

Single Char

• "a" → ["a"]

No Palindrome

• "abc" → []

Even Length

• "aabb" → ["abba", "baab"]

Both handle these well.

Complexity Breakdown

• Backtracking:
• Time: O(k * 2^k)—k unique chars.
• Space: O(n)—results.
• Recursive:
• Time: O(n!)—all perms.
• Space: O(n!)—perms.

Backtracking is leaner.

Key Takeaways

• Backtracking: Build halves smartly.
• Recursive: Try all, filter later.
• Palindromes: Mirror with one odd max.
• Python Tip: Dicts count chars—see [Python Basics](/python/basics).

Final Thoughts: Craft Palindromes Like a Pro

LeetCode 267: Palindrome Permutation II in Python is a creative string adventure. The backtracking solution crafts palindromes efficiently, while recursive perms explore every option. Want more? Try LeetCode 266: Palindrome Permutation or LeetCode 5: Longest Palindromic Substring. Ready to shuffle? Head to Solve LeetCode 267 on LeetCode and create those palindromes today!