Smallest Palindromic Rearrangement I - Solution & Explanation

Problem Overview: You are given a string and must rearrange its characters to form a palindrome. Among all valid palindromes, return the lexicographically smallest one. If the characters cannot form a palindrome, the rearrangement is impossible. The challenge is balancing palindrome constraints with lexicographic ordering.

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

The most direct idea is to generate every permutation of the string and check whether it forms a palindrome. For each valid palindrome, track the lexicographically smallest candidate. While this demonstrates the problem mechanics, the factorial growth makes it unusable for realistic input sizes. Even for moderate strings, the number of permutations explodes quickly. This approach mainly serves as a conceptual baseline showing why a smarter counting strategy is necessary.

Approach 2: Sort + Greedy Palindrome Construction (Time: O(n log n), Space: O(n))

Sort the characters first so lexicographically smaller letters appear earlier. Then count occurrences while building the palindrome greedily. Add half of each character's occurrences to the left side, track a single odd-count character for the center, and mirror the left side to form the right half. Sorting guarantees that smaller characters are placed earlier in the palindrome, producing the smallest valid arrangement. This approach is intuitive and works well, but the sort step adds an O(n log n) cost.

Approach 3: Frequency Counting (Optimal) (Time: O(n + k), Space: O(k))

The optimal solution replaces sorting with frequency counting. Use an array or hash map to count occurrences of each character in the string. For a palindrome to exist, at most one character may have an odd frequency. Build the left half by iterating characters in alphabetical order and appending freq[c] / 2 copies of each. If a character has an odd count, place one instance in the center. Finally, mirror the left half to create the right half.

This method effectively behaves like counting sort. Because characters are processed in sorted order implicitly through the frequency array, the resulting palindrome is automatically the smallest lexicographically. No explicit sorting is needed, which reduces the complexity to linear time relative to the input size.

Recommended for interviews: The frequency counting approach is what interviewers expect. It shows you understand palindrome constraints, lexicographic ordering, and how to replace sorting with counting. Mentioning the brute force approach briefly demonstrates problem exploration, but implementing the counting-based construction proves strong mastery of sorting and frequency techniques.