Given a string, find the next smallest palindrome

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.

O(N), Where ‘N’ is the length of the given string ‘S’.

Here, since we are iterating over all the characters in the number string ‘S’ which is of length ‘N’. Therefore the time complexity grows by order O(N).

O(1),

Since we are using constant space here so the space complexity becomes O(1).