Next smaller Palindrome

Easy
0/40
Average time to solve is 10m
profile
Contributed by
67 upvotes
Asked in companies
Deutsche BankAmazonSprinklr

Problem statement

You are given a number 'N' in the form of a string 'S', which is a palindrome. You need to find the greatest number strictly less than 'N' which is also a palindrome.

Note: 
1. A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward, such as madam, racecar, 1234321, etc.
2. The numerical value of the given string S will be greater than 0.
3. A single-digit number is also considered a palindrome.
4. The answer number should not contain any leading zeros, except for the case when the answer is 0.
5. Note that the length of the string is nothing but the number of digits in N.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer T denoting the number of test cases.

The first and the only line of each test case contains a string 'S', denoting the number whose next smaller palindrome is to be found.
Output Format: 
The only line of output of each test case should contain a string, denoting the next smaller palindrome of 'S'.

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= |S| <= 10^4

Where |S| donates the size of string 'S'.

Time Limit: 1sec
Sample Input 1:
1
12321
Sample Output 1:
12221
Explanation For Sample Input 1:
The next smaller palindrome to 12321 is 12221, as it is strictly less than 12321 and it reads the same from the front and back both.
Sample Input 2:
2
11
101
Sample Output 2:
9
99
Approaches (1)
Brute Force
  • Given the fact that the input number is a palindrome itself makes this problem very trivial.
  • Let us assume that the given string str is a palindrome, so we know that ‘S’ comprises of two halves  ‘S1’ and ‘S2’ i.e ‘S’ = ‘S1' + ‘S2', where ‘S1' and ‘S2’ are two strings, and ‘S2’ is the reverse of ‘S1’(in case of odd length palindromes ‘S2’ won’t have the last character of ‘S1’). So a change in any of the half must also reflect in the other half to keep the output string a palindrome.
  • So what we can do is either traverse ‘S1' from the end or ‘S2’ from the beginning i.e from the middle of the string str to any of the direction, because in this way we would have the option of updating lesser significant digits first.
  • Let us traverse ‘S2'from the beginning:
  1. If we find a position in ‘S2' such that ‘S2'['POS'] != 0 (digit at ‘S2'['POS'] is not equal to 0), we can simply update ‘S2'['POS'] = ‘S1'['N' - 1 - 'POS'] = ‘S2'['POS'] - 1 ( considering the size of ‘S’  = ‘N’  and 0-based indexing) and we are done i.e we have reduced the current number and we simply return the string.
  2. However, if ‘S2'['POS'] = 0, then we cant decrease this digit, and we will look further for non-zero digits. But before going ahead we need to make ‘S2'['POS'] = ‘S1'['N' - 1 - 'POS'] = 9, as we want the greatest number less than the current number, so if we keep this digit(and its corresponding digit in ‘S1') as it is and decrease some more significant digit, then this will not be the correct answer. For eg., next smaller palindrome of 2002 will be 1991 and not 1001.
  3. There is one last case in this approach: Consider the number 1001, now for this number we cant reduce the most significant 1(and it’s corresponding 1 in ‘S2') to 0 because in such a case the number would have leading zeros, so what we do is the two zeros will be converted to 9 and two ones will be discarded and one extra 9 will be added. This is done because, as we can see 1001 is 4 digit number, and 99 is a 2 digit number, so we add an extra 9, and thus the answer will be 999.

    

Time Complexity

O(N), where ‘N’ is the length of the given palindrome.

 

As we are iterating once through the string, hence the overall time complexity will be O(N).

Space Complexity

O(1)

 

Constant extra space is used.

Code Solution
(100% EXP penalty)
Next smaller Palindrome
Full screen
Console