Solution: Next Palindrome Using Same Digits

Statement

Given a numeric string, num_str, representing a palindromeA palindrome is a number that reads the same backward as it does forward. (composed only of digits). Return the smallest palindrome larger than num_str that can be created by rearranging its digits. If no such palindrome exists, return an empty string "".

Consider the following example to understand the expected output for a given numeric string:

• input string = "123321"

• The valid palindromes made from the exact digits are "213312", "231132", "312213", "132231", "321123".

• We return the palindrome "132231" because it is the smallest palindrome larger than the input string "123321".

Constraints:

• $1 \leq$ num_str.length $\leq 10^5$

• num_str is a palindrome.

Solution

We can use the two pointer technique to find the next larger palindrome efficiently. We start by dividing the palindrome into its left half. As a palindrome reads the same forwards and backward, we only need to rearrange the left half of the string and mirror it to form the right half.

• Identify the left half: For a given number, split it into its left half. For even-length numbers, split them equally. Keep the middle digit fixed for odd-length numbers and work only with the left half.

Here’s a quick demonstration for both cases: