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 string num_str
representing a
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:
num.length
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:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.