Smallest Palindromic Number Strictly Greater Than n, Up to 18 Digits
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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
```python
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**
```text
Input: n = "12932"
Output: "13031"
```
`12921` is the largest palindrome below `n`, and no palindrome lies strictly between `12932` and `13031`.
**Example 2**
```text
Input: n = "99"
Output: "101"
```
No two-digit palindrome is greater than `99`; the smallest three-digit palindrome is `101`.
**Example 3**
```text
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.
Overview: Given a positive integer of up to 18 digits as a string, return the smallest palindromic number strictly greater than it, or the input itself when no such palindrome stays within 18 digits. Tests digit-level reasoning and edge cases such as palindromic inputs, carries and changes in digit count.
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. Return it as a decimal string.
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.
### 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^31 - 1` and even `2^53`, so they are passed and returned as strings in every language; 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**
```text
Input: n = "12932"
Output: "13031"
```
`12921` is the largest palindrome below `n`, and no palindrome lies strictly between `12932` and `13031`.
**Example 2**
```text
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.
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^31 - 1 and 2^53, so they are passed and returned as decimal 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
- The result has at most 18 digits; if no palindrome p satisfies n < p <= 999999999999999999, return n unchanged
Examples
Input: ('1',)
Expected Output: '2'
Explanation: Smallest valid input; every single digit is a palindrome, so the next one is 2.
Input: ('9',)
Expected Output: '11'
Explanation: No single digit exceeds 9, so the answer grows to the smallest two-digit palindrome.
Hints
- Decide the answer's digit count first: can it have the same number of digits as n, or must it be longer?
- 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.
- Only a few inputs have no eligible answer: those where every larger palindrome would need more than 18 digits.