Next Smallest Palindrome | InterviewBit | Solution Explained in Detail

I explain the solution to Next Smallest Palindrome using basic intuitions and an observations based approach along with easy to understand examples. Problem Link.

0. Next Smallest Palindrome: Problem Discussion

0.0. IO Format

• input:
  • string, A
• output:
  • a string representing the next smallest palindrome, after A
• constraints:
  • 1 <= len(A) <= 100

0.1. Examples

• “23545” –> “23632”
• “99” -> “101”

1. Next Smallest Palindrome: First Thoughts

This looks one of those questions which is loaded with edge cases. Best way looks to split out the test cases as necessary.

2. Next Smallest Palindrome: Observations & Logic

2.0. Palindromes

The first thing we note from the example “99” is that we need to be able to detect palindromes, so that we can find the next one – we don’t want to return the same number again!

It looks like a good idea to create a function to do this, as we may need it later. For now, here’s a cheap implementation in Python3 (you should also know how to write it yourself!).

class Solution:
    def is_palindrome(self, a):
        return a == a[::-1]

Ok so what next? If we have a palindrome, we need to be able to add 1 to the number, so that we can then treat it as a normal number. This will simplify our life.

Below is a cheap implementation of add_1, which may/not work for all languages.

class Solution:
    def add_1(self, x):
        return str(int(x) + 1)

The below implementation is for the non-python people:

class Solution:
    def add_1(self, x):
        ns = ""
        carry = 1

        for c in reversed(x):
            d, r = divmod(int(c) + carry, 10)
            ns += str(r)
            carry = d
        if carry: ns += str(carry)

        return ns[::-1]

2.1. What Next?

Okay great! We can now handle palindrome cases, but what next?

We need to now handle the general cases. Whenever stuck in situations like this, always, always write down some test cases and see what happens. For now I will take odd length cases, then we will see what happens for even length cases.

2.2. Odd Cases

• “23545” –> “23632”, since we can go to 600s (the mid position) instead of 500s and repeat the flipped 23 substring
• “97531” –> “97579”, since we don’t need to go to 600s and we can stay at 500s and repeat the left substring, flipped to the right.

It looks like flipping the left substring is a common pattern. To formalize:

• get the right and left substrings (middle not included).
• check if the left substring is greater than right substring.
  • True: copy paste the reversed left substring in-place of right
  • False: increase the middle value by 1 and then do the same as above:
• return the new string

With the example:

• “23545” –> left = “23”, mid = “5”, right = “45”
• “23” > “45”?
  • False: mid = “5” –> mid = “6”. Then, “23” + “6” + “32” (“23” reversed)

Edge case:

• what if the mid digit is 9? like in “23945″. In that case, we need to add 1, but the 9 will become 10. So, the number becomes “24045”. We can then proceed as usual, but this becomes an important point – increasing the middle by 1 can have consequences that affect the left substring. Perhaps we can consider merging the left substring and the mid character?

Ok great! We are done then? NOPE! Feel free to experiment and write down some test cases that do not work with the current logic.

Done? I’ll show you one: “53545”.

• “53545” –> left = “53”, mid = “5”, right = “45”
• is left > right? === “53” > “45”?
  • True: so, the answer is “53” + “5” + “35” = “53535”

Something does look off aye? The number we returned is lesser than the one we started. That’s because of one big flaw. We don’t compare left with right, but reversed left with right. That’s because when returning, we have left + mid + reversed(left) kind of logic. So, it only makes sense to compare right with the reversed left.

2.3. A Quick Breather

Whew! We figured out quite a lot. There are two things we need to implement as of now. One is the function to compare two strings, and the other is to find the answer for odd length cases.

class Solution:
    def compare(self, left, right):
        for l, r in zip(left, right):
            if l > r: return 1
            elif l < r: return -1
            else: continue
        return 0

class Solution:
    def handle_odd(self, a):
        n = len(a)
        mid = n // 2
        left = a[:mid]
        right = a[mid+1:]
        
        if self.compare(left[::-1], right) == 1:
            return left + a[mid] + left[::-1]
        else:
            left = left + a[mid]
            left = self.add_1(left)
            
            return left + left[::-1][1:]

2.4. Even Cases

All right, let’s come back to logic. This time we will discuss even cases. Examples:

• “2363” –> “2442”
• “3428” –> “3443”

These look pretty much the same as the odd cases. To formalize,

• find the left and right substrings
• reversed(left) > right?
  • True: return left + reversed(left)
  • False: add 1 to left and do the same as above

class Solution:
    def handle_even(self, a):
        n = len(a)
        mid = n // 2
        left = a[:mid]
        right = a[mid:]
        
        if self.compare(left[::-1], right) == -1:
            left = self.add_1(left)
            return left + left[::-1]
        else:
            return left + left[::-1]

2.5. One Last Edge Case

We are almost done, but there’s one teeny tiny case that still remains. This case wasn’t obvious for me the first time. The case is that of single digits.

See, with our logic, if we get an input like “5”, we will see its a palindrome (yes we still check for that!) and then add 1 to it. Now “6” is an odd length case, so we extract the left = “”, right= “”. Since they are the same, we go to the else condition and add 1 more. Now, we finally return “7”.

Incorrect! We should have returned at “6” itself. So, we will add just one more line in the implementation. If the number after adding one to it, is also a palindrome, we can return early.

And with this, we are done!

3. Next Smallest Palindrome: Optimized Implementation

3.0. Code

class Solution:
    def is_palindrome(self, a):
        return a == a[::-1]
    
    def compare(self, left, right):
        for l, r in zip(left, right):
            if l > r: return 1
            elif l < r: return -1
            else: continue
        return 0
        
    def add_1(self, x):
        ns = ""
        carry = 1

        for c in reversed(x):
            d, r = divmod(int(c) + carry, 10)
            ns += str(r)
            carry = d
        if carry: ns += str(carry)

        return ns[::-1]
    
    def handle_odd(self, a):
        n = len(a)
        mid = n // 2
        left = a[:mid]
        right = a[mid+1:]
        
        if self.compare(left[::-1], right) == 1:
            return left + a[mid] + left[::-1]
        else:
            left = left + a[mid]
            left = self.add_1(left)
            
            return left + left[::-1][1:]
        
    def handle_even(self, a):
        n = len(a)
        mid = n // 2
        left = a[:mid]
        right = a[mid:]
        
        if self.compare(left[::-1], right) == -1:
            left = self.add_1(left)
            return left + left[::-1]
        else:
            return left + left[::-1]

    def solve(self, a):
        if self.is_palindrome(a): a = self.add_1(a)
        if self.is_palindrome(a): return a

        n = len(a)

        if n & 1:
            return self.handle_odd(a)
        else:
            return self.handle_even(a)

3.1. Complexity Analysis

• Time: O(N), where N is the length of the input string. We need to iterate over the string multiple times, for different purposes, but it would never exceed O(N) time.
• Space: O(N), since string operations like “[::-1]” make copies of the original string.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.