Smallest Palindromic Number Strictly Greater Than n, Up to 18 Digits

Given a positive integer n written as a decimal string, return the smallest integer that is strictly greater than n and is a palindrome, meaning its decimal digits read the same from left to right and from right to left. Results are limited to the same range as the input, at most 18 digits: if no palindrome p satisfies n < p <= 999999999999999999, return n unchanged.

Function Signature

def next_palindrome(n: str) -> str:

Rules

• Numbers are written in decimal without leading zeros, and the result is returned in the same form.
• Every single-digit number is a palindrome.
• The result must be strictly greater than n, even when n is itself a palindrome; for example, "808" gives "818".
• Eligible results have at most 18 digits. If no eligible palindrome is greater than n, return n.

Constraints

• 1 <= len(n) <= 18; n contains only the digits 0 to 9 and has no leading zero, so its value is between 1 and 10^18 - 1.
• Values can exceed 2^53, so they are passed as strings; every eligible value fits in a signed 64-bit integer.
• The gap between n and the answer can exceed 10^9, so testing numbers one at a time is too slow.

Examples

Example 1

Input:  n = "12932"
Output: "13031"

12921 is the largest palindrome below n, and no palindrome lies strictly between 12932 and 13031.

Example 2

Input:  n = "99"
Output: "101"

No two-digit palindrome is greater than 99; the smallest three-digit palindrome is 101.

Example 3

Input:  n = "999999999999999999"
Output: "999999999999999999"

The smallest palindrome greater than n is 1000000000000000001, which has 19 digits and is therefore not eligible, so n is returned.

Next Palindrome Within 18 Digits

Hints

1. Decide the answer's digit count first: can it have the same number of digits as n, or must it be longer?
2. Two decimal strings of equal length without leading zeros compare in the same order as the numbers they represent, so the 18-digit values never need to be converted.
3. Only a few inputs have no eligible answer: those where every larger palindrome would need more than 18 digits.

Approach

Let L = len(n). Case 1, every digit is 9: no L-digit palindrome exceeds n, and the smallest palindrome with L + 1 digits is 1, then L - 1 zeros, then 1. That value is eligible only when L + 1 <= 18, so for L = 18 (n = 999999999999999999) n is returned unchanged. Case 2, otherwise: the L-digit all-nines number is a palindrome greater than n, so the answer has exactly L digits. An L-digit palindrome is fully determined by its prefix, the first ceil(L/2) digits, and palindromes of length L are ordered exactly as their prefixes are. Invariant: a palindrome whose prefix is smaller than n's prefix is smaller than n, and one whose prefix is larger is greater than n. So the only candidate sharing n's prefix is the mirror M (prefix followed by the reversed first floor(L/2) digits). If M > n, M is the answer. Otherwise, which includes every palindromic n, the answer is the mirror of prefix + 1. The increment turns trailing 9s into 0s and carries left. It never overflows the prefix length, because an all-nines prefix mirrors to the all-nines number, which would already exceed n. Both strings have the same length, so comparing digit strings is the same as comparing numbers, and no 64-bit or big-integer arithmetic is needed. Edge cases: single digits (1 -> 2, 9 -> 11), all-nines inputs that gain a digit, palindromic inputs that must move strictly upward, carries through the middle digit (12932 -> 13031), and the 18-digit ceiling.

• Time complexity: O(L), where L = len(n) <= 18
• Space complexity: O(L)