# 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

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.

``````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.

``````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/