Palindrome Permutation II

Palindrome Permutation II

What is this problem about?

The Palindrome Permutation II problem asks you to generate all unique palindromes that can be formed from a given string's characters. Unlike the check version, this requires generating all valid palindromic permutations. This coding problem uses backtracking on the half of the palindrome, then mirrors it. The hash table, backtracking, and string interview pattern is the core.

Why is this asked in interviews?

Meta asks this as an extension of Palindrome Permutation I to test backtracking on a reduced problem space. Since a palindrome is symmetric, you only need to generate permutations of the half-string and mirror them. This halves the backtracking space.

Algorithmic pattern used

Frequency halving + backtracking. Count frequencies. If more than one character has odd frequency, return [] (impossible). Halve all frequencies (take floor). Identify the optional middle character (the one with odd frequency, if any). Generate all unique permutations of the half-characters using backtracking. For each half permutation, build the palindrome: half + middle + reversed(half).

Example explanation

s="aabb". Frequencies: a=2, b=2. Half: a=1, b=1. Middle: "". Permutations of "ab": "ab","ba". Palindromes: "abba","baab". Result: ["abba","baab"].

s="aabbc". Half: a=1, b=1. Middle="c". Permutations of "ab": "ab","ba". Palindromes: "abcba","bacab". Result: ["abcba","bacab"].

Common mistakes candidates make

• Generating all permutations of the full string (too slow, many invalid ones).
• Not halving frequencies before backtracking.
• Generating duplicate palindromes (handle same adjacent characters in backtracking).
• Not including the middle character correctly.

Interview preparation tip

Palindrome generation through backtracking is much more efficient when you exploit the symmetric structure — generate only the first half. The deduplication logic in backtracking (skip same character if previous same was skipped) prevents duplicate outputs. Practice unique permutation generation first, then apply it to palindrome half-generation. The mirroring step at result collection is the elegant final piece.