Domain 2MediumCORE

Palindrome Permutation II

We are given a string s and need to return every unique permutation of that string which forms a palindrome. If no palindromic permutations exist, we return an empty list.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Backtracking

267. Palindrome Permutation II

Model: qwen3.5:9b
Topics: Backtracking
FAANG asked: 0
Acceptance rate: 37.6%


Problem Breakdown

We are given a string s and need to return every unique permutation of that string which forms a palindrome. If no palindromic permutations exist, we return an empty list.

Key constraints:

  1. Palindrome Property: A valid palindrome can have at most one character with an odd frequency count (which would sit in the center). All other characters must appear an even number of times.
  2. Uniqueness: The output list must not contain duplicate strings, even if the input string contains identical characters that could theoretically be swapped to form “different” permutations.

Intuition

  1. Feasibility Check First: Before generating anything, we validate if a palindrome is possible using character counts. If more than one character has an odd count, return [] immediately. This prunes the search space significantly for invalid inputs like Example 2 (“abc”).
  2. Symmetry Reduction: A palindrome reads the same forwards and backwards. We only need to generate permutations of the first half of the string (excluding the center). Once we have a valid left-half permutation, mirroring it creates the full palindrome. This reduces complexity from N!N! to roughly (N/2)!(N/2)!.
  3. Handling Duplicates: Since input characters can be identical (e.g., “aabb”), standard backtracking on indices would generate duplicates (“abba” via first ‘a’ vs second ‘a’). To avoid this, we should track character frequencies rather than treating every instance as distinct during the permutation generation phase.

Approach

  1. Count Frequencies: Use a hash map (or array) to count occurrences of each character in s.
  2. Validate & Prepare Half String:
    • Iterate through counts and identify characters with odd frequencies. If more than one exists, return empty list.
    • Construct the “half string” by taking half the frequency (count // 2) for every character. Store these in a map or list to be permuted.
  3. Backtracking (DFS):
    • Define a recursive function dfs(current_path).
    • At each step, iterate through available characters from our “half string” frequency map. If a char is still available (count > 0), decrement its count and recurse with the new path.
    • Backtrack by incrementing the count to explore other permutations.
  4. Construct Result: When current_path length equals half of original string, construct full palindrome: path + center_char + reverse(path). Add to results list.

Complexity Analysis

  • Time Complexity: O(N⋅K!)O(N \cdot K!) where NN is the number of characters in input and K=N/2K = N/2. The dominant factor is generating unique permutations for half the string length (K!K!). However, since we divide by factorial counts of identical chars (multiset permutation), it’s effectively bounded by (N/2)!×(number of valid palindromes)(N/2)! \times (\text{number of valid palindromes}). Given N≤16N \le 16, this fits well within time limits.
  • Space Complexity: O(N)O(N) for the recursion stack depth and storing character counts, plus space required to store the output list (which is proportional to total characters in all result strings).

Solution

from collections import Counter
from typing import List

class Solution:
    def generatePalindromes(self, s: str) -> List[str]:
        # Step 1: Count frequencies of each character
        char_count = Counter(s)
        
        # Step 2: Validate palindrome possibility and prepare half-string counts
        odd_char_count = sum(1 for count in char_count.values() if count % 2 != 0)
        
        # If more than one character has an odd frequency, no palindromic permutation exists
        if odd_char_count > 1:
            return []
            
        center_char = ""
        half_counts = {}
        
        for char in char_count:
            count = char_count[char]
            if count % 2 != 0:
                # If there is exactly one odd character, it goes to the center
                center_char = char 
            # Add only half of each character's occurrences to our permutation pool
            half_counts[char] = count // 2
            
        result = []
        
        def backtrack(path):
            # Base case: if path length equals number of chars in half_counts, we have a valid left-half
            if len(path) == sum(half_counts.values()):
                full_palindrome = path + center_char + path[::-1]
                result.append(full_palindrome)
                return
            
            for char in list(half_counts.keys()): 
                if half_counts[char] > 0:
                    # Choose character
                    half_counts[char] -= 1
                    backtrack(path + char)
                    
                    # Un-choose (Backtrack)
                    half_counts[char] += 1
                    
        backtrack("")
        
        return result

Edge Cases Handled

  • No Palindrome Possible: If input is “abc” or any string with >1 odd-count characters, the validation step returns [].
  • Single Character Input: E.g., “a”. Odd count = 1. Center=“a”, half_counts={}. Backtrack immediately hits base case (len=0), result=[“a”]. Correct.
  • All Same Characters: E.g., “aaaa”. Half counts={‘a’:2}. Permutations generate [“aa”]. Output [“aaaa”]. Correct (no duplicates).
  • Empty String: Constraints say 1 <= s.length, so not applicable per spec, but logic holds for empty input as well.