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.