Last Updated: 17 Nov, 2020
Given a string, find the next smallest palindrome
Easy
Asked in companies
You are given a number 'N' in the form of a string 'S', your task is to find the smallest number strictly greater than the given number 'N' which is 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 'naman', 'abcba', '1234321', etc
2) The numerical value of the given string 'S' will be greater than 0.
3) A single-digit number is also considered as a palindrome.
4) Note that the length of the string 'S' is nothing but the number of digits in the number 'N'.
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains an integer, denoting the number of digits in the number 'N' (i.e. the length of the string).
The second line of each test case contains the string 'S'.
Output Format:
The only line of output of each test case consists of the next greater palindromic number(as described in the problem statement) returned in the form of a string.
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 <= len(S) <= 10^4
Time Limit : 1 sec
Approaches
In this method, Before we start let us define what is the right half (or right part) and what is left half (or left part) in the string. There can be two cases based on the length of the string:
- Case-1: (Odd length string), consider the string “1234567”, the part of the string “123” is the left part(or left half) and the part “567” is the right part(or right half), and the one left(4) is called the middle of the string.
This number can also be represented as:
1234567= 1*10^6 + 2*10^5 + 3*10^4 + 4*10^3 + 5*10^2 + 6*10^1 + 7*10^0.
From this, we can derive a conclusion that the left part contains more significant digits (digits with greater place value) as compared to the right part.
- Case-2: (Even length string), consider the string “123456”, the part of the string “123” is the left part(or left half) and the part “456” is the right part(or right half), and the one left in black is called the middle of the string.
So The algorithm for the problem would be as follows:
- At the start, we will add one to the number represented by the string because we want the smallest palindrome which is strictly greater than the input string. For example, if the input string is 999 then we will perform all the operations on 1000 (i.e.999+1).
- Maintain two pointers i and j pointing at the start and the end of the string respectively, and a boolean variable to keep a track of violation of the condition( i.e. the palindrome should be smallest possible palindrome greater than the input string).
- Now we will run a loop until both the pointers cross each other(i.e. while(i<=j)).
- On each iteration, we will copy the digit on the left half to the corresponding position in the right half. For example, consider the string “12345” (Red represents the position of pointer i and blue represents the position of pointer j), so now after the specified operation the string will become “12341”.
- While copying the digit we will check whether the being copied is greater than the digit already present their or not. If the digit being copied is greater then we will set the value of this variable to false, and if the digit is smaller then we will set the value of this variable to true. (Because we want a palindrome greater than the current number) and will update the value of variable pos( variable to maintain the position of the last character where the condition failed i.e. the last index where the value of the boolean variable was set of true). For example in the above case, the copied digit(1) is smaller than the digit already present there(5), so the value of the boolean variable will be set to true.
- And if the digits are equal we will check if the digit is not equal to 9 and the value of the boolean variable is true then we will make pos equal to the position of this number.
- After completion of the loop, we will check if the value of the boolean variable is true(indicating that the number we formed is still not greater than the given number). If the value of the boolean variable is true then:
- we will add one to the digit at index pos(last index where condition failed), and we will simultaneously increase the digit in its corresponding right half(to maintain the property of palindrome as well as increase the number).
- For example, consider the string “12345” (Red colour denotes the character at index pos). After performing the above operation on this string the string becomes “13335”, the right counterpart of any index i can be calculated as (counterpart = length(string)-1-i), considering 0-based indexing of the string.
- As we have made our palindrome greater than the given number, now to make the smallest such palindrome we will loop through all the characters starting from index ‘pos+1’ up to the middle character of the string and as we traverse a character we will make that character and its corresponding right counter equal to ‘0’ (To make this palindrome the smallest possible palindrome which is greater than the given number and since we have made the palindrome greater so now our only task is to make this smallest possible so to do this we perform the specified operation).
- Return the string calculated after completing all the above operations.