1public class ClosestPalindrome {
2    private static long mirrorPalindrome(String str) {
3        char[] chars = str.toCharArray();
4        int n = chars.length;
5        for (int i = 0; i < n / 2; i++) {
6            chars[n - 1 - i] = chars[i];
7        }
8        return Long.parseLong(new String(chars));
9    }
10    
11    public static String closestPalindrome(String n) {
12        int len = n.length();
13        long original = Long.parseLong(n);
14        long best = Long.MAX_VALUE;
15        String result = "";
16
17        // Generate basic, lower and higher mirroring
18        StringBuilder lower = new StringBuilder(n);
19        StringBuilder higher = new StringBuilder(n);
20
21        long mirrorValue = mirrorPalindrome(n);
22
23        // Compare different mirroring options
24        if (mirrorValue != original) best = mirrorValue;
25
26        char lowerChar = lower.charAt((len-1)/2);
27        lower.setCharAt((len-1)/2, lowerChar == '0' ? '9' : (char)(lowerChar - 1));
28        long lowMirror = mirrorPalindrome(lower.toString());
29        if (Math.abs(lowMirror - original) < Math.abs(best - original) || (Math.abs(lowMirror - original) == Math.abs(best - original) && lowMirror < best)) {
30            best = lowMirror;
31        }
32
33        char higherChar = higher.charAt((len-1)/2);
34        higher.setCharAt((len-1)/2, (char)(higherChar + 1));
35        long highMirror = mirrorPalindrome(higher.toString());
36        if (Math.abs(highMirror - original) < Math.abs(best - original) || (Math.abs(highMirror - original) == Math.abs(best - original) && highMirror < best)) {
37            best = highMirror;
38        }
39
40        result = Long.toString(best);
41        return result;
42    }
43}