# Find the Closest Palindrome

`String`, `Math`

Hard

Given an integer n, find the closest integer (not including itself), which is a palindrome.

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

**Example 1:**

```
Input:
 "123"

Output:
 "121"
```

**Note:**

1. The input **n** is a positive integer represented by string, whose length will not exceed 18.
2. If there is a tie, return the smaller one as answer.

## Solution

### Based on: @fun4LeetCode's answer:

<https://leetcode.com/problems/find-the-closest-palindrome/discuss/102389/Java-solution-with-detailed-proof>

8 ms, faster than 98.75%

3 steps:

`I -- The given number itself is a palindrome`

`II -- The given number is a not palindrome`

`III -- Construct the whole palindrome from its left part`

Construct a palindrome based on left half, then find the nearest palindrome larger or smaller than `curP`: nextP, prevP. Then compare the diff between num, cur, prev, next.

```java
class Solution {
    public String nearestPalindromic(String n) {
        if (n == null || n.isEmpty()) {
            return "";
        }
        char[] p = n.toCharArray();
        for (int i = 0, j = p.length - 1; i < j; i++, j--) {
            p[j] = p[i];
        }

        String curP = String.valueOf(p);
        String prevP = nearestPalindromeOf(curP, false);
        String nextP = nearestPalindromeOf(curP, true);

        long num = Long.valueOf(n);
        long cur = Long.valueOf(curP);
        long prev = Long.valueOf(prevP);
        long next = Long.valueOf(nextP);

        long d1 = Math.abs(num - cur);
        long d2 = Math.abs(num - prev);
        long d3 = Math.abs(num - next);

        if (num == cur) {
            return d2 <= d3 ? prevP : nextP;
        } else if (num > cur) {
            return d1 <= d3 ? curP : nextP;
        } else {
            return d2 <= d1 ? prevP : curP;
        }
    }

    /**
    * @param s - input palindrome string
    * @param dir true if finding larger, false if finding smaller
    * @return nearest palindrome string of input palindrome
    */
    public String nearestPalindromeOf(String s, boolean dir) {
        int len = s.length();
        int k = len / 2;
        // make sure left include the mid point if len is odd number
        int base = Integer.valueOf(s.substring(0, len - k)); 
        base += dir ? 1 : -1;

        // handle "11", "1" case
        if (base == 0) {
            if (k == 0) {
                return "0";
            }
            return "9";
        }

        StringBuilder left = new StringBuilder(String.valueOf(base));
        StringBuilder right = new StringBuilder(left).reverse();
        // handle "1001", "10001" type of case
        if (k > left.length()) {
            right.append("9");
        }

        return left.append(right.substring(right.length() - k)).toString();
    }

}
```

### LeetCode official

Using Math:

* Time complexity : O(l). Scanning, insertion, deletion,, mirroring takes O(l), wherellis the length of the string.
* Space complexity : O(l). Temporary variables are used to store the strings.

```java
public class Solution {
    public String mirroring(String s) {
        String x = s.substring(0, (s.length()) / 2);
        return x + (s.length() % 2 == 1 ? s.charAt(s.length() / 2) : "") + new StringBuilder(x).reverse().toString();
    }
    public String nearestPalindromic(String n) {
        if (n.equals("1"))
            return "0";

        String a = mirroring(n);
        long diff1 = Long.MAX_VALUE;
        diff1 = Math.abs(Long.parseLong(n) - Long.parseLong(a));
        if (diff1 == 0)
            diff1 = Long.MAX_VALUE;

        StringBuilder s = new StringBuilder(n);
        int i = (s.length() - 1) / 2;
        while (i >= 0 && s.charAt(i) == '0') {
            s.replace(i, i + 1, "9");
            i--;
        }
        if (i == 0 && s.charAt(i) == '1') {
            s.delete(0, 1);
            int mid = (s.length() - 1) / 2;
            s.replace(mid, mid + 1, "9");
        } else
            s.replace(i, i + 1, "" + (char)(s.charAt(i) - 1));
        String b = mirroring(s.toString());
        long diff2 = Math.abs(Long.parseLong(n) - Long.parseLong(b));


        s = new StringBuilder(n);
        i = (s.length() - 1) / 2;
        while (i >= 0 && s.charAt(i) == '9') {
            s.replace(i, i + 1, "0");
            i--;
        }
        if (i < 0) {
            s.insert(0, "1");
        } else
            s.replace(i, i + 1, "" + (char)(s.charAt(i) + 1));
        String c = mirroring(s.toString());
        long diff3 = Math.abs(Long.parseLong(n) - Long.parseLong(c));

        if (diff2 <= diff1 && diff2 <= diff3)
            return b;
        if (diff1 <= diff3 && diff1 <= diff2)
            return a;
        else
            return c;
    }
}
```

## Reference

<https://leetcode.com/problems/find-the-closest-palindrome/solution/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/string/find-the-closest-palindrome.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.