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:

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

Difficulty: interview

Starter code:

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        

Solutions:
class Solution:
     def nearestPalindromic(self, num):
         """
         :type n: str
         :rtype: str
         """
         K = len(num)
         candidates = set([10**K + 1, 10**(K-1) - 1])
         Prefix = int(num[:(K+1)//2])
 
         for start in map(str, [Prefix-1, Prefix, Prefix+1]):
             candidates.add(start + [start, start[:-1]][K & 1][::-1])
 
         candidates.discard(num)
 
         return str(min(candidates, key=lambda x: (abs(int(x) - int(num)), int(x))))


class Solution:
     def nearestPalindromic(self, n):
         """
         :type n: str
         :rtype: str
         """
         K = len(n)
         candidates = [str(10**k + d) for k in (K-1, K) for d in (-1, 1)]
 
         Prefix = int(n[:(K+1)//2])
 
         for start in map(str, [Prefix - 1, Prefix, Prefix + 1]):
             candidates.append(str(start) + (start[:-1] if K % 2 == 1 else start)[::-1])
 
         ans, diff = 0, float('inf')
         base = int(n)
 
         for C in candidates:
             b = int(C)
             d = abs(b - base)
 
             if d == 0 or d > diff or (d == diff and b > ans):
                 continue
 
             ans = int(C)
             diff = d
 
         return str(ans)


class Solution:
     def nearestPalindromic(self, n):
         """
         :type n: str
         :rtype: str
         """
         K = len(n)
         candidates = [str(10**k + d) for k in (K-1, K) for d in (-1, 1)]
         prefix = n[:(K+1)//2]
         P = int(prefix)
         for start in map(str, (P-1, P, P+1)):
             candidates.append(start + (start[:-1] if K%2 else start)[::-1])
 
         def delta(x):
             return abs(int(n) - int(x))
 
         ans = None
         for cand in candidates:
             if cand != n and not cand.startswith('00'):
                 if (ans is None or delta(cand) < delta(ans) or
                         delta(cand) == delta(ans) and int(cand) < int(ans)):
                     ans = cand
         return ans


class Solution:
     def nearestPalindromic(self, n):
         """
         :type n: str
         :rtype: str
         """
         evenPal = lambda sp : int(sp + sp[::-1])
         oddPal = lambda sp : int(sp + sp[::-1][1:])
         sn, n = n, int(n)
         if len(sn) == 1: return str(n - 1)
         ans = -999999999999999999
         mid = len(sn) // 2
         for sp in sn[:mid], sn[:mid + 1], str(int(sn[:mid]) * 10):
             p = int(sp)
             for pal in evenPal, oddPal:
                 for d in -1, 0, 1:
                     val = pal(str(p + d))
                     if val == n: continue
                     ans = min(ans, val, key = lambda x : (abs(x - n), x))
         return str(ans)


class Solution:
     def getPalindromic(self,num,mid=''):
         return str(num)+mid+str(num)[::-1]
     def nearestPalindromic(self,n):
         """
         :type n: str
         :rtype: str
         """
         if len(n)==1:
             return str(int(n)-1)
         midstr='' if len(n)%2==0 else n[len(n)//2]
         midint=-1 if len(n)%2==0 else int(n[len(n)//2])
         s=['']*6
         # 99..99
         s[0]='9'*(len(n)-1)
         # (l-1)m(l-1)
         s[1]=self.getPalindromic(int(n[:(len(n))//2])-1,midstr)
         # l(m-1)l
         s[2]=n[:len(n)//2]+str(midint-1)+n[:len(n)//2][::-1] if midint>0 else self.getPalindromic(int(n[:len(n)//2])-1)
         # lml
         s[3]=n[:len(n)//2]+midstr+n[:len(n)//2][::-1]
         # l(m+1)l
         s[4]=n[:len(n)//2]+str(midint+1)+n[:len(n)//2][::-1] if midint<10 and midint>-1 else self.getPalindromic(int(n[:len(n)//2])+1)
         # 10..01
         s[5]='1'+'0'*(len(n)-1)+'1'
         nums=map(lambda x:abs(int(x)-int(n)),s)
         nums=list(map(lambda x:x if x>0 else 1e18,nums))
         return s[nums.index(min(nums))]