564. Find the Closest Palindrome

T: O(1), only 5 cadidates, and gen Palindromic only needs len/2 (so 18/2 = 9)

S: O(1)

class Solution {
    public String nearestPalindromic(String n) {
        int len = n.length();
        long cur = Long.valueOf(n);

        boolean isEvenLen = len % 2 == 0;
        int leftIndex = isEvenLen ? len/2-1 : len/2;  // 10 -> len=2, true, 0
        String leftPart = n.substring(0, leftIndex+1); // 0, 1, so left = 1
        long left = Long.valueOf(leftPart);

        List<Long> list = new ArrayList<>();
        list.add(getPalindrome(left, isEvenLen)); // left = 1, this gen 11
        list.add(getPalindrome(left+1, isEvenLen)); // left + 1 = 1+1= 2 -> 2 generate 22
        list.add(getPalindrome(left-1, isEvenLen)); // left - 1 = 0 -> 0 gen 0
        list.add((long)Math.pow(10, len-1)-1); // ex: n = 10, this get 9
        list.add((long)Math.pow(10, len)+1); // this get 101 (can for n = 99)
        // when n = 10 get-> 5 candidates: [11, 22, 0, 9, 101]
        long diff = Long.MAX_VALUE;
        long result = 0;
        for (long p : list) {
            if (cur == p) {
                continue;
            }

            if (diff > Math.abs(cur - p)) {
                diff = Math.abs(cur - p);
                result = p;
            } else if (diff == Math.abs(cur - p)) { // if the same diff, but smaller number
                result = Math.min(result, p);
            }
            
        }
        return String.valueOf(result);
    }
    
    private long getPalindrome(long left, boolean even) {
        long res = left;
        if (!even) {
            left /= 10;
        }
        while (left > 0) {
            res = res * 10 + left%10;
            left /= 10;
        }
        return res;
    }
}

/*
5 cases
if n = 12345

leftPart 123 -> 12321
leftPart+1 124 -> 12421
leftPart-1 122 -> 12221
or 
10^(len-1)-1 -> 10000-1= 9999
10^(len)+1 -> 100000+1 = 100001

if n = 123456
leftPart 123 -> 123321
leftPart+1 124 -> 124421
leftPart-1 122 -> 122221
or 
10^(len-1)-1 -> 100000-1= 99999
10^(len)+1 -> 1000000+1 = 1000001

even len or odd len

odd len
xxx
12345

even len 
012
xxx
123456

res = 1234
left = 123

12340 + 3

left = 12
1234321

2222

2221

129
131


142
141

606
599
595

1331
1234
1221

1441
1249
1221


12345 , false

12345
123450 + 0

01234
1234 56


! even -> 

123
12

12321

res = 12
left = 1
res = 123 * 10 + 12%10 = 1230 + 2 = 1232...
res = 1232 & 10 + 1%10 = 12320+1 = 12321
12321

 */