Next Smallest Palindrome Larger Than a Number

Problem

Given a number as a string, find the next smallest palindrome strictly larger than this number. The input and output are both strings representing non-negative integers (possibly with leading zeros).

Examples

Example 1

1
2
3

Input: num = "23545"
Output: "23632"
Explanation: The next palindrome after 23545 is 23632.

Example 2

1
2
3

Input: num = "999"
Output: "1001"
Explanation: The next palindrome after 999 is 1001.

Solution

Method 1 – Mirror and Increment (String Version)

Intuition

The key idea is that the next palindrome greater than a given number can be constructed by reflecting (mirroring) the left half of the number onto the right half. If this mirrored number is already greater than the original, it is the answer. If not, we need to increment the middle digit(s) and mirror again. Special care is needed for numbers made entirely of ‘9’s, as the next palindrome in that case is always of the form “100…001”.

Let’s see this with examples:

• For num = "23545":

  • Mirror the left half (“23”) to the right: get “23632”.
  • “23632” is greater than “23545”, so this is the answer.

• For num = "999":

  • All digits are ‘9’, so the answer is “1001” (one more digit, with zeros in the middle).

• For num = "12321":

  • Mirror left half (“12”) to right: get “12321” (same as input).
  • Increment the middle digit (“3” → “4”): get “12421”.
  • Mirror again: “12421” is the answer.

This approach works because the smallest palindrome greater than a number must be as close as possible to the original, and mirroring the left half achieves this. If the mirrored value is not enough, incrementing the middle and mirroring again ensures the next closest palindrome.

Approach

Let’s break down the steps in detail:

1. Check for all ‘9’s:

• If every digit is ‘9’, the answer is always “1” + (n-1 zeros) + “1”. For example, “999” → “1001”.

2. Mirror the left half to the right:

• Copy the left half of the string and overwrite the right half with its mirror.
• For even length, mirror up to the middle; for odd length, leave the middle digit as is.
• Example: “23545” → mirror “23” to get “23632”.

3. Compare mirrored string to original:

• If the mirrored string is greater than the original, return it.
• Example: “23632” > “23545” → return “23632”.

4. If not, increment the middle digit(s):

• If the mirrored string is not greater, increment the middle digit (for odd length) or the left half (for even length), handling any carry.
• After incrementing, mirror the left half to the right again.
• Example: “12321” → mirror gives “12321” (same as input), increment middle to get “12421”.

5. Return the result:

• The resulting string is the next smallest palindrome.

Step-by-step walkthrough for Example 1:

Input: num = "23545"

1. Not all ‘9’s.
2. Mirror left half (“23”) to right: “23632”.
3. “23632” > “23545” → return “23632”.

Step-by-step walkthrough for Example 2:

Input: num = "999"

1. All digits are ‘9’.
2. Return “1001”.

Step-by-step walkthrough for Example 3:

Input: num = "12321"

1. Not all ‘9’s.
2. Mirror left half (“12”) to right: “12321” (same as input).
3. Not greater, so increment the middle digit: “3” → “4”.
4. Mirror again: “12421”.
5. Return “12421”.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
  string nextPalindrome(string num) {
    int n = num.size();
    // Check if all digits are '9'
    if (count(num.begin(), num.end(), '9') == n)
      return "1" + string(n-1, '0') + "1";
    string ans = num;
    // Mirror left to right
    for (int i = 0; i < n/2; ++i) ans[n-1-i] = ans[i];
    if (ans > num) return ans;
    // Increment the middle
    int mid = (n-1)/2;
    while (mid >= 0 && ans[mid] == '9') ans[mid--] = '0';
    ans[mid]++;
    // Mirror again
    for (int i = 0; i < n/2; ++i) ans[n-1-i] = ans[i];
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
  public String nextPalindrome(String num) {
    int n = num.length();
    if (num.chars().allMatch(c -> c == '9'))
      return "1" + "0".repeat(n-1) + "1";
    char[] ans = num.toCharArray();
    for (int i = 0; i < n/2; ++i) ans[n-1-i] = ans[i];
    if (new String(ans).compareTo(num) > 0) return new String(ans);
    int mid = (n-1)/2;
    while (mid >= 0 && ans[mid] == '9') ans[mid--] = '0';
    ans[mid]++;
    for (int i = 0; i < n/2; ++i) ans[n-1-i] = ans[i];
    return new String(ans);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def next_palindrome(self, num: str) -> str:
        n = len(num)
        if all(c == '9' for c in num):
            return '1' + '0' * (n-1) + '1'
        ans = list(num)
        for i in range(n//2):
            ans[-1-i] = ans[i]
        if ''.join(ans) > num:
            return ''.join(ans)
        mid = (n-1)//2
        while mid >= 0 and ans[mid] == '9':
            ans[mid] = '0'
            mid -= 1
        ans[mid] = str(int(ans[mid]) + 1)
        for i in range(n//2):
            ans[-1-i] = ans[i]
        return ''.join(ans)

Complexity

• ⏰ Time complexity: O(n), since we scan and mirror the string at most twice.
• 🧺 Space complexity: O(n), for the answer string.