# LeetCode 564: Find the Closest Palindrome

## Problem Restatement

We are given a string `n` representing an integer.

Return the closest integer palindrome to `n`.

The returned palindrome must not be `n` itself.

If there are two palindromes with the same distance from `n`, return the smaller one.

The input length is at most `18`, so the number can be too large for some fixed-width integer languages, but Python can handle it directly. The official constraints say `1 <= n.length <= 18`, `n` contains only digits, has no leading zeros, and represents an integer in `[1, 10^18 - 1]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A numeric string `n` |
| Output | The closest different palindrome as a string |
| Tie rule | Return the smaller palindrome |
| Important detail | Do not return `n` itself |

Example function shape:

```python
def nearestPalindromic(n: str) -> str:
    ...
```

## Examples

Example 1:

```python
n = "123"
```

Nearby palindromes include:

| Palindrome | Distance |
|---|---:|
| `"121"` | `2` |
| `"131"` | `8` |
| `"111"` | `12` |

The closest is:

```python
"121"
```

Example 2:

```python
n = "1"
```

The closest palindromes are:

| Palindrome | Distance |
|---|---:|
| `"0"` | `1` |
| `"2"` | `1` |

There is a tie, so we return the smaller one:

```python
"0"
```

Example 3:

```python
n = "1000"
```

Nearby palindromes include:

```python
"999"
"1001"
```

Both are close, but:

```python
abs(1000 - 999) = 1
abs(1000 - 1001) = 1
```

Tie goes to the smaller palindrome, so the answer is:

```python
"999"
```

## First Thought: Search Outward

A direct idea is to check:

```python
n - 1
n + 1
n - 2
n + 2
...
```

and stop when we find a palindrome.

This is simple, but it can be far too slow.

For a number like:

```python
"100000000000000000"
```

we do not want to test many numbers one by one.

We need to construct only the palindromes that can be closest.

## Key Insight

A nearby palindrome is determined mostly by the left half of the number.

For example:

```python
n = "12345"
```

If we mirror the left half, we get:

```python
"12321"
```

This is often the closest candidate.

But sometimes we need to adjust the prefix by `-1` or `+1`.

For `"12345"`, the relevant prefixes are:

```python
122
123
124
```

Mirroring them gives:

```python
12221
12321
12421
```

The closest palindrome must be among these prefix-based candidates, plus boundary cases.

## Boundary Cases

Prefix mirroring alone does not handle changes in digit length.

For example:

| Input | Important boundary candidate |
|---|---|
| `"10"` | `"9"` |
| `"1000"` | `"999"` |
| `"999"` | `"1001"` |
| `"1"` | `"0"` |

So we always include:

```python
10^(length - 1) - 1
```

This is the largest palindrome with one fewer digit, such as `999`.

We also include:

```python
10^length + 1
```

This is the smallest palindrome with one more digit, such as `1001`.

## Candidate Generation

Let:

```python
length = len(n)
prefix_length = (length + 1) // 2
prefix = int(n[:prefix_length])
```

Then build candidates from:

```python
prefix - 1
prefix
prefix + 1
```

For each prefix candidate, mirror it into a palindrome of the same length style.

If the original length is even, mirror the full prefix:

```python
prefix = "12"
palindrome = "1221"
```

If the original length is odd, do not duplicate the middle digit:

```python
prefix = "123"
palindrome = "12321"
```

## Algorithm

1. Convert `n` to integer `original`.
2. Let `length = len(n)`.
3. Add boundary candidates:
   ```python id="xhuhx5"
   10 ** (length - 1) - 1
   10 ** length + 1
   ```
4. Extract the left prefix of length `(length + 1) // 2`.
5. For `prefix - 1`, `prefix`, and `prefix + 1`:
   1. Mirror the prefix into a palindrome.
   2. Add it to the candidate set.
6. Remove `original` from candidates if present.
7. Choose the candidate with the smallest pair:
   ```python id="xzm923"
   (abs(candidate - original), candidate)
   ```
8. Return it as a string.

The pair comparison handles the tie rule automatically. Smaller distance wins first. If distances tie, smaller candidate wins.

## Correctness

Any palindrome with the same number of digits is determined by its left half. To be close to `n`, its left half must be close to the left half of `n`.

If the left half differs by more than `1`, the resulting palindrome changes a more significant part of the number too much. A closer or equal candidate can be obtained by using `prefix - 1`, `prefix`, or `prefix + 1`.

These three mirrored candidates cover the closest same-length palindromes around `n`.

However, the nearest palindrome may also have one fewer digit or one more digit. This happens near powers of ten and all-nine numbers. The candidates `10^(length - 1) - 1` and `10^length + 1` cover those cases.

The algorithm checks all relevant candidates, excludes `n` itself, and chooses the one with minimum absolute difference. If two candidates have the same difference, it chooses the smaller value. Therefore, it returns exactly the required closest palindrome.

## Complexity

Let `d = len(n)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(d)` | We build a constant number of candidates, each with up to `d` digits |
| Space | `O(d)` | Candidate strings and integers have up to `d + 1` digits |

The number of candidates is constant.

## Implementation

```python
class Solution:
    def nearestPalindromic(self, n: str) -> str:
        original = int(n)
        length = len(n)

        candidates = {
            10 ** (length - 1) - 1,
            10 ** length + 1,
        }

        prefix_length = (length + 1) // 2
        prefix = int(n[:prefix_length])

        for value in (prefix - 1, prefix, prefix + 1):
            left = str(value)

            if length % 2 == 0:
                palindrome = left + left[::-1]
            else:
                palindrome = left + left[-2::-1]

            candidates.add(int(palindrome))

        candidates.discard(original)

        best = min(candidates, key=lambda x: (abs(x - original), x))
        return str(best)
```

## Code Explanation

We first store the original number as an integer:

```python
original = int(n)
```

Then we add the two digit-length boundary candidates:

```python
candidates = {
    10 ** (length - 1) - 1,
    10 ** length + 1,
}
```

For a length of `4`, these are:

```python
999
10001
```

Then we take the left half, including the middle digit for odd lengths:

```python
prefix_length = (length + 1) // 2
prefix = int(n[:prefix_length])
```

For example:

| n | Prefix |
|---|---|
| `"1234"` | `12` |
| `"12345"` | `123` |

We try the prefix itself and its neighbors:

```python
for value in (prefix - 1, prefix, prefix + 1):
```

For even length, we mirror the full prefix:

```python
palindrome = left + left[::-1]
```

For odd length, we skip duplicating the middle digit:

```python
palindrome = left + left[-2::-1]
```

Then we remove the input number itself:

```python
candidates.discard(original)
```

Finally, we choose by distance first, then value:

```python
best = min(candidates, key=lambda x: (abs(x - original), x))
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.nearestPalindromic("123") == "121"
    assert s.nearestPalindromic("1") == "0"
    assert s.nearestPalindromic("10") == "9"
    assert s.nearestPalindromic("11") == "9"
    assert s.nearestPalindromic("99") == "101"
    assert s.nearestPalindromic("1000") == "999"
    assert s.nearestPalindromic("999") == "1001"
    assert s.nearestPalindromic("121") == "111"
    assert s.nearestPalindromic("1283") == "1331"

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"123"` | Basic sample |
| `"1"` | Single digit tie case |
| `"10"` | Closest is one fewer digit |
| `"11"` | Input itself is a palindrome, must exclude it |
| `"99"` | Closest is one more digit |
| `"1000"` | Tie between `999` and `1001`, choose smaller |
| `"999"` | All nines become `1001` |
| `"121"` | Already palindrome |
| `"1283"` | Prefix adjustment upward |