Solution: Next Palindrome Using Same Digits

Statement

Given a string num_str representing a palindrome,A palindrome is a number that reads the same backward as forward. the string only contains digits. Your task is to return the next possible palindrome using the same digits. The returned palindrome would be the next largest palindrome, meaning there can be more than one way to rearrange the digits to make a larger palindrome. Return an empty string if no greater palindrome can be made.

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

• input string = "123321"

• possible palindromes = "213312", "231132", "312213", "132231", "321123"

• We should return the palindrome "132231" as it is greater than "123321" yet the smallest palindrome excluding the original palindrome.

Constraints:

• $1 \leq$ num.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 equally. Keep the middle digit fixed for odd length and work only with the left half.

Here’s a quick demonstration for both cases: