# Find the Closest Palindrome
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-closest-palindrome)
Canonical: https://scaleengineer.com/dsa/problems/find-the-closest-palindrome
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String
**Companies:** [Yelp](https://scaleengineer.com/companies/yelp)
---
## Problem
Given a string `n` representing an integer, return _the closest integer (not including itself), which is a palindrome_. If there is a tie, return _**the smaller one**_.

The closest is defined as the absolute difference minimized between two integers.

**Example 1:**

**Input:** n = "123"
**Output:** "121"

**Example 2:**

**Input:** n = "1"
**Output:** "0"
**Explanation:** 0 and 2 are the closest palindromes but we return the smallest which is 0.

**Constraints:**

* `1 <= n.length <= 18`
* `n` consists of only digits.
* `n` does not have leading zeros.
* `n` is representing an integer in the range `[1, 1018 - 1]`.

# Approaches
## Brute Force by Checking Neighbors
This approach involves converting the input string `n` to a number and then iteratively checking numbers smaller and larger than `n` until a palindrome is found in each direction. The one with the smaller absolute difference to `n` is the answer.
**Time:** O(10^(L/2) * L), where L is the length of `n`. The gap between a number and its nearest palindrome can be on the order of `10^(L/2)`. For each number in this gap, we perform a palindrome check which takes O(L) time. This complexity is too high for the given constraints. · **Space:** O(L), where L is the number of digits in `n`. This space is used to store the string representation of the numbers being checked.
**Pros:** Simple to understand and implement.; Logically straightforward.
**Cons:** Highly inefficient for larger inputs as the distance to the nearest palindrome can be large.; Will likely result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
The brute-force method is the most straightforward way to conceptualize the problem. The core idea is to search outwards from the given number `n` in both directions (decreasing and increasing) and stop at the very first palindrome encountered on each side.

1.  **Conversion:** The input string `n` is first converted into its numerical representation (e.g., a `long` in Java) to allow for arithmetic operations.
2.  **Downward Search:** We start a search for the largest palindrome that is smaller than `n`. This is done by initializing a variable `lower` to `n - 1` and decrementing it in a loop. In each iteration, we check if `lower` is a palindrome. The first number that satisfies this condition is our first candidate.
3.  **Upward Search:** Similarly, we search for the smallest palindrome that is larger than `n`. We initialize `upper` to `n + 1` and increment it until we find a palindrome.
4.  **Comparison:** After finding both `lower` and `upper` palindromes, we determine which one is closer to `n` by comparing the absolute differences `n - lower` and `upper - n`. According to the problem statement, if the differences are equal (a tie), we must choose the smaller palindrome, which is `lower`.
5.  **Result:** The chosen number is then converted back to a string and returned.

To check if a number is a palindrome, a helper function is used. It converts the number to a string and checks if the string reads the same forwards and backward, typically by using a two-pointer technique.

```java
class Solution {
    public String nearestPalindromic(String n) {
        long num = Long.parseLong(n);
        long lower = findLowerPalindrome(num - 1);
        long upper = findUpperPalindrome(num + 1);

        long diff1 = num - lower;
        long diff2 = upper - num;

        if (diff1 <= diff2) {
            return String.valueOf(lower);
        } else {
            return String.valueOf(upper);
        }
    }

    private long findLowerPalindrome(long limit) {
        long i = limit;
        while (true) {
            if (isPalindrome(String.valueOf(i))) {
                return i;
            }
            i--;
        }
    }

    private long findUpperPalindrome(long limit) {
        long i = limit;
        while (true) {
            if (isPalindrome(String.valueOf(i))) {
                return i;
            }
            i++;
        }
    }

    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Convert the input string `n` to a `long` variable `num`.
- Find the first palindrome smaller than `num`:
  - Initialize `lower = num - 1`.
  - Loop downwards from `lower`, checking if each number is a palindrome.
  - A number is checked by converting it to a string and verifying if the string is the same forwards and backward.
  - Stop when the first smaller palindrome is found.
- Find the first palindrome larger than `num`:
  - Initialize `upper = num + 1`.
  - Loop upwards from `upper`, checking if each number is a palindrome.
  - Stop when the first larger palindrome is found.
- Compare the absolute differences: `|num - lower|` and `|upper - num|`.
- If `|num - lower|` is less than or equal to `|upper - num|`, return `lower`. Otherwise, return `upper`.
- Convert the result back to a string.

## Constructing Palindrome Candidates
A more efficient approach is to realize that the closest palindrome to a number `n` must be structurally similar to `n`. The closest palindrome will likely have the same number of digits, or one more, or one less. We can generate a small, constant set of candidate palindromes based on this observation and find the best one among them.
**Time:** O(L), where L is the length of `n`. The number of candidates is constant (five). Generating each candidate involves string manipulations that take O(L) time. The final loop to find the best candidate runs a constant number of times. · **Space:** O(L), where L is the length of `n`. This space is used to store the candidate strings and other temporary strings during construction.
**Pros:** Extremely efficient with a constant number of candidates to check, regardless of the input size.; Optimal time complexity for the given constraints.; Correctly handles all edge cases by considering candidates with different numbers of digits.
**Cons:** The logic is more complex to devise and implement compared to the brute-force approach.; Requires careful handling of edge cases, such as constructing palindromes from prefixes of varying lengths.
### Explanation
Instead of searching linearly, we can intelligently construct a small set of candidate palindromes that are likely to be the closest. The key insight is that the closest palindrome to an integer `n` will have a number of digits equal to `n`, or `n-1`, or `n+1`.

This leads to a set of five primary candidates:

1.  **Largest Palindrome with One Fewer Digit:** This is always a sequence of nines (e.g., for `n=100`, this candidate is `99`). This can be calculated as `10^(L-1) - 1` where `L` is the length of `n`.
2.  **Smallest Palindrome with One More Digit:** This is always a `1` followed by `L-1` zeros and another `1` (e.g., for `n=99`, this is `101`). This can be calculated as `10^L + 1`.
3.  **Palindromes with the Same Number of Digits:** These are the most likely candidates. A palindrome is defined by its first half. We can take the first half of `n` (its prefix) and mirror it to form a palindrome. To account for the closest palindrome being slightly smaller or larger, we generate three candidates from the prefix of `n`:
    *   One from `prefix - 1`.
    *   One from `prefix` itself.
    *   One from `prefix + 1`.

For example, if `n = "123"`, the prefix is `"12"`. We generate palindromes from prefixes `11`, `12`, and `13`, which gives us `"111"`, `"121"`, and `"131"`.

After generating this constant set of (at most) five candidates, we iterate through them. For each candidate, we calculate its absolute difference from `n`. We keep track of the candidate that yields the minimum difference, making sure to handle ties by choosing the smaller value. The original number `n` itself is excluded from being a valid answer.

```java
import java.util.List;
import java.util.ArrayList;

class Solution {
    public String nearestPalindromic(String n) {
        long num = Long.parseLong(n);
        int len = n.length();
        List<Long> candidates = new ArrayList<>();

        // Candidate 1: 99...9 (L-1 digits)
        candidates.add((long) Math.pow(10, len - 1) - 1);
        // Candidate 2: 10...01 (L+1 digits)
        candidates.add((long) Math.pow(10, len) + 1);

        // Candidates with same number of digits
        String prefixStr = n.substring(0, (len + 1) / 2);
        long prefixVal = Long.parseLong(prefixStr);

        for (long p = prefixVal - 1; p <= prefixVal + 1; p++) {
            String pStr = String.valueOf(p);
            StringBuilder suffix = new StringBuilder(pStr).reverse();
            String palindromeStr;
            if (len % 2 != 0) {
                palindromeStr = pStr + suffix.substring(1);
            } else {
                palindromeStr = pStr + suffix.toString();
            }
            candidates.add(Long.parseLong(palindromeStr));
        }

        long minDiff = Long.MAX_VALUE;
        long result = -1;

        for (long candidate : candidates) {
            if (candidate == num) {
                continue;
            }
            long diff = Math.abs(candidate - num);
            if (diff < minDiff) {
                minDiff = diff;
                result = candidate;
            } else if (diff == minDiff) {
                result = Math.min(result, candidate);
            }
        }
        return String.valueOf(result);
    }
}
```
### Algorithm
- Let `n` be the input string and `L` be its length. Convert `n` to a `long` `num`.
- Initialize a list of candidates.
- Add two boundary candidates:
  - The largest palindrome with `L-1` digits: `(long)Math.pow(10, L - 1) - 1`.
  - The smallest palindrome with `L+1` digits: `(long)Math.pow(10, L) + 1`.
- Generate candidates with the same number of digits:
  - Get the prefix string: `prefixStr = n.substring(0, (L + 1) / 2)`.
  - Parse `prefixStr` to a `long` `prefixVal`.
  - Iterate `p` from `prefixVal - 1` to `prefixVal + 1`.
  - For each `p`, construct a full palindrome string of length `L` by mirroring the string of `p`.
  - Add these generated palindromes to the candidates list.
- Find the best candidate:
  - Initialize `minDiff = Long.MAX_VALUE` and `result`.
  - Iterate through each `candidate` in the list.
  - Skip the candidate if it's equal to `num`.
  - Calculate `diff = Math.abs(candidate - num)`.
  - If `diff` is smaller than `minDiff`, update `minDiff` and `result`.
  - If `diff` is equal to `minDiff`, update `result` to be the smaller of the current `result` and the `candidate`.
- Return the final `result` as a string.

# Solutions
### Java

```java
class Solution {
public
  String nearestPalindromic(String n) {
    long x = Long.parseLong(n);
    long ans = -1;
    for (long t : get(n)) {
      if (ans == -1 || Math.abs(t - x) < Math.abs(ans - x) ||
          (Math.abs(t - x) == Math.abs(ans - x) && t < ans)) {
        ans = t;
      }
    }
    return Long.toString(ans);
  }
private
  Set<Long> get(String n) {
    int l = n.length();
    Set<Long> res = new HashSet<>();
    res.add((long)Math.pow(10, l - 1) - 1);
    res.add((long)Math.pow(10, l) + 1);
    long left = Long.parseLong(n.substring(0, (l + 1) / 2));
    for (long i = left - 1; i <= left + 1; ++i) {
      StringBuilder sb = new StringBuilder();
      sb.append(i);
      sb.append(new StringBuilder(i + "").reverse().substring(l & 1));
      res.add(Long.parseLong(sb.toString()));
    }
    res.remove(Long.parseLong(n));
    return res;
  }
}

```

### JavaScript

```javascript
/** * @param {string} n * @return {string} */ function nearestPalindromic ( n ) { const x = BigInt ( n ); let ans = null ; for ( const t of getCandidates ( n )) { if ( ans === null || absDiff ( t , x ) < absDiff ( ans , x ) || ( absDiff ( t , x ) === absDiff ( ans , x ) && t < ans ) ) { ans = t ; } } return ans . toString (); } function getCandidates ( n ) { const length = n . length ; const res = new Set (); res . add ( BigInt ( Math . pow ( 10 , length - 1 ) - 1 )); res . add ( BigInt ( Math . pow ( 10 , length ) + 1 )); const left = BigInt ( n . substring ( 0 , Math . ceil ( length / 2 ))); for ( let i = left - 1 n ; i <= left + 1 n ; i ++ ) { const prefix = i . toString (); const t = prefix + prefix . split ( '' ) . reverse () . slice ( length % 2 ) . join ( '' ); res . add ( BigInt ( t )); } res . delete ( BigInt ( n )); return res ; } function absDiff ( a , b ) { return a > b ? a - b : b - a ; }

```

### CPP

```cpp
class Solution {
public:
  string nearestPalindromic(string n) {
    long x = stol(n);
    long ans = -1;
    for (long t : get(n))
      if (ans == -1 || abs(t - x) < abs(ans - x) ||
          (abs(t - x) == abs(ans - x) && t < ans))
        ans = t;
    return to_string(ans);
  }
  unordered_set<long> get(string &n) {
    int l = n.size();
    unordered_set<long> res;
    res.insert((long)pow(10, l - 1) - 1);
    res.insert((long)pow(10, l) + 1);
    long left = stol(n.substr(0, (l + 1) / 2));
    for (long i = left - 1; i <= left + 1; ++i) {
      string prefix = to_string(i);
      string t = prefix + string(prefix.rbegin() + (l & 1), prefix.rend());
      res.insert(stol(t));
    }
    res.erase(stol(n));
    return res;
  }
};

```

### Python

```python
class Solution:
    def nearestPalindromic(self, n: str) -> str: x = int(n) l = len(n) res = {10 ** (l - 1) - 1, 10 ** l + 1} left = int(n[: (l + 1) >> 1]) for i in range(left - 1, left + 2): j = i if l % 2 == 0 else i // 10 while j: i = i * 10 + j % 10 j //= 10 res . add(i) res . discard(x) ans = - 1 for t in res: if (ans == - 1 or abs(t - x) < abs(ans - x) or (abs(t - x) == abs(ans - x) and t < ans)): ans = t return str(ans)

```