Palindrome Permutation II - Solution & Explanation

Problem Overview: Given a string s, generate all unique permutations that form a palindrome. If no palindromic arrangement exists, return an empty list. The challenge is detecting whether a palindrome is possible and avoiding duplicate permutations.

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

This method generates every permutation of the string and checks whether each permutation is a palindrome. Use standard permutation generation with recursion or backtracking, then verify the result using a two-pointer palindrome check. The drawback is factorial growth: n! permutations are generated even though only a tiny subset could be valid palindromes. Duplicate permutations also appear when characters repeat, which requires additional filtering using a set. This approach works only for very small strings and mainly demonstrates baseline reasoning.

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

A palindrome is symmetric. At most one character can appear an odd number of times. Start by counting character frequencies using a hash table. If more than one character has an odd frequency, forming a palindrome is impossible. Otherwise, build a half string containing freq[c] / 2 copies of each character. The center character (if any) is the one with the odd count.

Next, generate unique permutations of this half string using backtracking. Sorting or using a visited array prevents duplicate permutations when characters repeat. For every generated half permutation, construct the palindrome as half + middle + reverse(half). Because only half of the characters are permuted, the search space drops from n! to (n/2)!, which is dramatically smaller.

This method leverages symmetry and frequency counting to prune invalid cases early. The main operations are counting characters, recursively generating permutations of the half string, and mirroring it using simple string manipulation. Memory usage remains linear because only the recursion stack and frequency structures are stored.

Recommended for interviews: Interviewers expect the hash map + half-permutation backtracking solution. Recognizing the palindrome property (only one odd frequency allowed) shows strong problem decomposition. Mentioning the brute force permutation approach first shows understanding of the search space, but the optimized half-generation technique demonstrates algorithmic insight and practical efficiency.