Smallest Palindromic Rearrangement II - Solution & Explanation

Problem Overview: You are given a string and must rearrange its characters to form palindromes. Among all valid palindromic rearrangements, return the k-th lexicographically smallest one. If fewer than k palindromes exist, return an empty string. The challenge is efficiently counting how many palindromes can be formed from the remaining characters while constructing the answer.

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

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 the half-string containing freq[c] / 2 copies of each character. Generate all permutations of this half-string, mirror them around the center character (if one exists), and store the resulting palindromes. After sorting lexicographically, return the k-th palindrome. This approach demonstrates the palindrome construction logic but quickly becomes infeasible because permutations grow factorially.

Approach 2: Lexicographic Construction with Combinatorics (Optimal) (Time: O(26 * n), Space: O(26))

Instead of generating every permutation, compute how many palindromes can be formed from the remaining characters. Count character frequencies with a hash table and build the half-frequency array. The palindrome is determined entirely by the order of this half. Iterate characters from 'a' to 'z' and tentatively place one character in the current position of the half-string. Use combinatorics to calculate how many permutations remain with the updated counts using factorial division: (remaining)! / (freq1! * freq2! ...). If this count is smaller than k, skip those permutations and subtract from k. Otherwise, fix that character and continue building the half. After the half-string is finalized, mirror it and insert the optional middle character to produce the full palindrome. This avoids generating permutations and relies on counting instead.

The core idea is treating palindrome construction as a permutation problem on half the characters. Efficient counting lets you skip entire blocks of permutations and directly construct the desired result.

Recommended for interviews: The combinatorics-based lexicographic construction is the expected approach. Brute force shows you understand how palindromes form, but interviewers typically look for the counting insight that avoids enumerating permutations. Combining string manipulation with combinatorial counting demonstrates strong algorithmic reasoning.