Find the Next Larger Palindrome

Given a positive integer n, return the smallest integer strictly greater than n whose decimal representation is a palindrome.

A palindrome reads the same from left to right and right to left. Do not allow leading zeros.

Examples:

• n = 9 -> 11
• n = 123 -> 131
• n = 808 -> 818
• n = 999 -> 1001

Discuss edge cases such as single-digit inputs, numbers consisting only of 9s, even versus odd digit lengths, and inputs that are already palindromes.

Find the Next Larger Palindrome

Given a positive integer n, return the smallest integer strictly greater than n whose decimal representation is a palindrome.

A palindrome reads the same from left to right and right to left. The result must not contain leading zeros.

Examples:

• 9 -> 11
• 123 -> 131
• 808 -> 818
• 999 -> 1001

Be careful with edge cases such as single-digit inputs, numbers made entirely of 9s, even versus odd digit lengths, and inputs that are already palindromes. A brute-force approach that checks every number after n is not efficient enough; instead, reason about how palindromes are formed.

Constraints

• 1 <= n < 10^18
• The returned palindrome must have no leading zeros

Hints

1. Try building a palindrome by copying the left half of the number onto the right half.
2. If that mirrored number is not strictly greater than n, increment the middle digit(s) and mirror again. Numbers like 9, 99, and 999 need special handling.