Next Smaller Palindrome Problem Statement

You are given a palindrome number represented as a string S. Your task is to find the largest palindrome number that is strictly less than S.

Example:

Input:

T = 2
S₁ = "12321"
S₂ = "98789"

Output:

"12221"
"98689"

Explanation:

For S₁ = "12321", the largest palindrome less than it is "12221".
For S₂ = "98789", the largest palindrome less than it is "98689".

Constraints:

1 ≤ T ≤ 100

1 ≤ |S| ≤ 10⁴, where |S| denotes the size of string 'S'.

Question

You are given a palindrome number represented as a string S. Your task is to find the largest palindrome number that is strictly less than S.

T = 2
S₁ = "12321"
S₂ = "98789"

"12221"
"98689"

For S₁ = "12321", the largest palindrome less than it is "12221".
For S₂ = "98789", the largest palindrome less than it is "98689".

Accepted Answer

Find the largest palindrome number strictly less than a given palindrome number.

Iterate from the middle towards the start and end of the string to find the largest palindrome less than the given number.
If the number is odd in length, simply decrement the middle digit. If it is even, decrement the middle two digits.
Handle cases where the resulting number might have leading zeros by removing them.

Deutsche Bank Software Developer Intern interview questions & answers