Solution: Next Palindrome Using Same Digits

Let’s solve the Next Palindrome Using Same Digits problem using the Two Pointers pattern.

We'll cover the following

Statement

Given a numeric string, numStr, 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 numStr 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≤1 \leq numStr.length ≤105\leq 10^5

  • numStr 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:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.