Introduction

Given a decimal number as a string, the goal is to find the smallest palindrome that is strictly larger than it. A brute-force loop that keeps adding one and checking for symmetry works, but it becomes painfully slow once the input has many digits.

The efficient solution uses the structure of palindromes directly. Instead of searching every number, you mirror the left side onto the right side and only increment the middle when the mirrored candidate is not large enough.

Why Brute Force Is the Wrong Baseline

Suppose the input is 1234567898765000. The next palindrome is close, but a naive loop may still perform thousands of string conversions and palindrome checks before it arrives there. In the worst case, the gap can be large enough that the running time is dominated by repeated trial values rather than the actual size of the number.

A better target is linear time in the number of digits, written as O(n). That is possible because the next palindrome depends only on a small part of the input:

• the left half
• the middle digit, for odd lengths
• carry propagation when you increment that controlling portion

Mirror First, Then Increment

The core idea is simple:

1. Copy the left half onto the right half.
2. If that mirrored number is already greater than the input, you are done.
3. Otherwise, increment the middle of the number and mirror again.

For example, with 23545:

• Mirroring the left side gives 23532.
• That is smaller than the input.
• Increment the middle-controlled part and mirror again.
• The result becomes 23632.

For 12021:

• Mirroring gives 12021.
• It is not strictly larger.
• Increment the middle and mirror again.
• The result is 12121.

Handling Carries Correctly

The only tricky part is carry propagation. When the center contains 9, incrementing may roll into the digits on the left.

Consider 12921:

• Mirroring gives 12921, which is equal to the input.
• Increment the middle digit 9, which causes a carry.
• The center becomes 0, the left side 12 becomes 13.
• Mirroring produces 13031.

The all-9 case needs special treatment. If the input is 9, 99, or 999, the next palindrome has one more digit:

• '9 becomes 11'
• '99 becomes 101'
• '999 becomes 1001'

That pattern is easy to build directly as 1, followed by zeros, followed by 1.

Python Implementation

The following implementation works on strings, so it is safe for numbers larger than the machine integer range:

1def next_palindrome(number: str) -> str:
2    if set(number) == {"9"}:
3        return "1" + ("0" * (len(number) - 1)) + "1"
4
5    digits = list(number)
6    n = len(digits)
7
8    def mirror_in_place() -> None:
9        left = 0
10        right = n - 1
11        while left < right:
12            digits[right] = digits[left]
13            left += 1
14            right -= 1
15
16    original = digits[:]
17    mirror_in_place()
18    if "".join(digits) > "".join(original):
19        return "".join(digits)
20
21    carry = 1
22    left = (n - 1) // 2
23    right = n // 2
24
25    while left >= 0 and carry:
26        new_digit = (ord(digits[left]) - ord("0")) + carry
27        carry = new_digit // 10
28        digits[left] = str(new_digit % 10)
29        digits[right] = digits[left]
30        left -= 1
31        right += 1
32
33    return "".join(digits)
34
35
36examples = ["12345", "12921", "999", "808", "1991"]
37for value in examples:
38    print(value, "->", next_palindrome(value))

Example output:

112345 -> 12421
212921 -> 13031
3999 -> 1001
4808 -> 818
51991 -> 2002

Why This Runs in Linear Time

There are two passes that matter:

• one pass to mirror the left side to the right
• one pass to propagate a carry from the center toward the front

Each pass touches at most n digits, so the algorithm runs in O(n) time and uses O(n) space because the string is stored as a mutable list of characters.

This is dramatically better than brute force for long inputs. Even for a hundred-digit number, the algorithm still only scans the digits a constant number of times.

Common Pitfalls

Many incorrect solutions fail for equality. If the mirrored candidate is exactly the same as the input, it is not the answer because the problem asks for the next larger palindrome, not the current one.

Another common bug is updating only the left side during carry propagation and forgetting to mirror the same digit onto the right side. That creates a number that is larger but no longer a palindrome.

The all-9 case is easy to overlook. Without a separate check, code often overflows the middle logic and produces the wrong length.

Finally, avoid converting very large strings into built-in integer types unless the language guarantees arbitrary precision and you actually need arithmetic on the full number. This problem is mostly positional, so string or array logic is usually cleaner and safer.

Summary

• The efficient approach is mirror first, then increment the middle only if needed.
• The naive add-and-check strategy wastes work and does not scale to large inputs.
• Carry propagation from the center is the main implementation detail to get right.
• Inputs made entirely of 9 need a dedicated rule such as 999 -> 1001.
• A string-based solution runs in O(n) time and works for very large numbers.