Lexicographically Smallest Palindromic Permutation Greater Than Target - Solution & Explanation

Problem Overview: Given a string, return the lexicographically smallest palindromic permutation that is strictly greater than the target string. If no such palindrome exists, return an empty string. The key constraint is that the resulting string must both be a permutation of the characters and remain a palindrome.

Approach 1: Brute Force Enumeration (Factorial Time, O(n!) time, O(n) space)

The direct strategy is to generate every permutation of the string, filter the ones that form palindromes, and keep the smallest palindrome that is lexicographically greater than the target. You check each permutation by comparing characters from both ends using two pointers. While easy to reason about, the permutation space grows as n!, which becomes infeasible even for moderate string sizes. This approach mainly demonstrates the constraints of the problem rather than serving as a practical solution.

Approach 2: Half String Permutation + Next Lexicographic Order (Optimal) (O(n log n) time, O(n) space)

A palindrome is fully determined by its first half. Count the frequency of each character in the string. Build a sorted half-string using freq[c] // 2 copies of each character and keep a middle character if any count is odd. Construct the smallest palindrome by mirroring this half. If that palindrome is already greater than the target, return it.

If not, compute the next lexicographic permutation of the half-string using the classic next_permutation technique: scan from the right to find the first decreasing position, swap with the next larger character, then reverse the suffix. Each time a new half is produced, mirror it to rebuild the palindrome and compare with the target. This works because lexicographic ordering of palindromes corresponds directly to ordering of their first halves. The process effectively enumerates valid palindromes in sorted order without exploring the entire permutation space.

Approach 3: Enumeration with Early Pruning (O(n · k) time, O(n) space)

Another view treats the half-string generation as controlled enumeration. Build candidate halves character by character while maintaining lexicographic ordering. If a prefix already exceeds the corresponding prefix of the target's half, the remaining positions can be filled with the smallest characters. This prunes large parts of the search space compared to brute force. It is conceptually useful but typically more complex than simply applying next_permutation.

Recommended for interviews: The half-string permutation with next_permutation is the approach interviewers expect. It leverages the structural property of palindromes and reduces the search space from n! permutations to permutations of only half the string. Showing the brute force idea demonstrates understanding of the problem space, while the optimized method shows algorithmic maturity and familiarity with lexicographic permutation techniques.