Palindrome Permutation II - Solution & Explanation

Problem Overview: Given a string s, generate all distinct permutations that form a palindrome. If no palindromic permutation exists, return an empty list. The challenge is avoiding duplicate permutations while ensuring the string structure satisfies palindrome rules.

Approach 1: Generate All Permutations + Palindrome Check (Brute Force) (Time: O(n! * n), Space: O(n))

This method generates every permutation of the string using standard backtracking and checks each permutation to see if it reads the same forward and backward. After building a permutation, run a two-pointer palindrome check from both ends toward the center. A hash set prevents duplicate results. The approach is simple but extremely inefficient because it explores n! permutations even when most cannot possibly be palindromes.

Approach 2: Frequency Map + Half Permutation Backtracking (Time: O((n/2)! * n), Space: O(n))

A palindrome has strict character frequency rules: at most one character can have an odd count. Use a hash table to count characters and immediately return an empty list if more than one odd frequency appears. Build only half of the palindrome by taking count / 2 copies of each character. Run backtracking on this half-string to generate unique permutations while skipping duplicates. For each half permutation, mirror it and optionally insert the odd character in the center to produce the full palindrome. This reduces the search space dramatically because only (n/2)! permutations are explored instead of n!.

Approach 3: Frequency Map + Direct Palindrome Construction (Time: O((n/2)! * n), Space: O(n))

Instead of explicitly generating a half string first, maintain a frequency map and construct the palindrome from both ends during recursion. Each step chooses a character with frequency ≥ 2, places it at the left and right positions, and decreases its count by two. Continue until the string is filled, inserting the odd-frequency character in the center when needed. This approach avoids building an intermediate half array and works directly with counts, which can reduce memory overhead while still using backtracking over valid character pairs.

Recommended for interviews: The frequency-map half-permutation approach is the expected solution. Interviewers want to see the palindrome frequency insight first, then efficient permutation generation without duplicates. Brute force demonstrates understanding of permutations but fails scalability. Combining hash table counting with controlled backtracking shows strong algorithmic reasoning.