Next Palindrome Using Same Digits - Solution & Explanation

Problem Overview: Given a numeric string that is already a palindrome, return the next larger palindrome that can be formed using exactly the same digits. If no larger palindrome exists, return an empty string. The result must preserve the palindrome structure while using the same multiset of digits.

Approach 1: Generate Permutations and Check Palindromes (Brute Force) (Time: O(n! * n), Space: O(n))

A naive strategy generates permutations of the digits and filters the ones that form valid palindromes. For each permutation, verify the palindrome condition by comparing characters from both ends using two pointers. Track the smallest palindrome strictly larger than the original value. This approach is impractical for large inputs because factorial growth quickly becomes unmanageable. It mainly helps illustrate the constraints of the problem: the palindrome structure means only half the digits actually determine the entire number.

Approach 2: Next Permutation of the First Half (Optimal) (Time: O(n), Space: O(n))

The key observation: a palindrome is fully determined by its first half. The second half is just the mirror of the first. Instead of permuting all digits, operate only on the left half of the string. Extract the first n/2 digits and compute the next lexicographically greater permutation using the standard next-permutation algorithm. This involves scanning from right to left to find the first decreasing element, swapping it with the next larger digit on its right, and reversing the suffix.

Once the next permutation of the left half is formed, rebuild the palindrome. If the length is even, mirror the entire half. If the length is odd, keep the middle digit unchanged and mirror only the left portion around it. Because next permutation guarantees the smallest lexicographically larger arrangement, the constructed palindrome is the next valid one using the same digits.

This method uses simple string manipulation and the classic permutation pattern while maintaining the palindrome invariant. The algorithm scans the string a few times, so the complexity stays linear.

Recommended for interviews: Interviewers expect the next-permutation insight. Recognizing that only the first half controls the palindrome drastically reduces the search space. Mentioning the brute-force idea shows understanding of the constraints, but implementing the half-permutation approach demonstrates strong algorithmic reasoning and familiarity with permutation patterns.