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 of the number and decrement the digits to create the largest palindrome less than the given number.
Handle cases where the number is all '9's by changing the middle digit to '9' and decrementing the rest of the digits.
If the number has an odd length, simply mirror the first half to create the largest palindrome less than the given number.

ZIGRAM Software Developer interview questions & answers