Next greater palindrome

You are given a string n holding a positive integer in decimal, with no leading zeros. It can be hundreds of digits long, so it may not fit in any built-in integer type.

Return the smallest palindrome that is strictly greater than n, also as a decimal string. A palindrome reads the same forwards and backwards.

def next_greater_palindrome(n: str) -> str

Constraints

• 1 <= len(n) <= 10^5
• n has only the digits 0-9 and does not start with 0.
• If n is already a palindrome, the answer must still be strictly greater.
• Aim for time linear in the number of digits.

Example 1

Input:  n = "4352"
Output: "4444"

Mirroring the left half 43 gives 4334, which is smaller than 4352. The next palindrome with four digits is 4444.

Example 2

Input:  n = "999"
Output: "1001"

No three-digit palindrome is greater than 999, so the answer has one more digit.