Problem statement

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

Solution

First of all, there is not more than 5 candidates we need to consider for number n. Let us cut first half and denote this number by half. For example for 1234567 it will be 1234 and for 123456 it will be 123. Then we need to consider numbers half - 1, half, half + 1 and reconstruct palindromes from them: I use two functions: Co(q) and Ce(q). Also we need to consider numbers 99...99 and 100...001.

Complexity

Overall time and space complexity is O(k), where k is length of number n.

Code

class Solution:
    def nearestPalindromic(self, n):
        def Co(q): return int(str(q) + str(q)[::-1])
        def Ce(q): return int(str(q) + str(q)[:-1][::-1])
        k = len(n)
        if k % 2 == 0:
            half = int(n[:k//2])
            c1, c2, c3 = Co(half), Co(half-1), Co(half+1)
        else:
            half = int(n[:k//2+1])
            c1, c2, c3 = Ce(half), Ce(half-1), Ce(half+1)
        
        cands = set([10**k+1, 10**(k-1)-1]) | set([c1, c2, c3])
        cands.discard(int(n))
       
        return str(min(cands, key = lambda x: [abs(x-int(n)), x]))