<p>Given a string <code>n</code> representing an integer, return <em>the closest integer (not including itself), which is a palindrome</em>. If there is a tie, return <em><strong>the smaller one</strong></em>.</p>

<p>The closest is defined as the absolute difference minimized between two integers.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = &quot;123&quot;
<strong>Output:</strong> &quot;121&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = &quot;1&quot;
<strong>Output:</strong> &quot;0&quot;
<strong>Explanation:</strong> 0 and 2 are the closest palindromes but we return the smallest which is 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n.length &lt;= 18</code></li>
	<li><code>n</code> consists of only digits.</li>
	<li><code>n</code> does not have leading zeros.</li>
	<li><code>n</code> is representing an integer in the range <code>[1, 10<sup>18</sup> - 1]</code>.</li>
</ul>

'''
up to 18 digits, always at least 1, so base case return 0 

well any single digit is a palindrome
we're also trying to change the units to match the hundreds before
or more generally, if we take a middle split, we want to change the rhs over lhs
since its cheaper / smaller distance
and by definition as a palindrome, if even we want to consider the middle two, if odd, the center one

eg 10 -> could be 9 or 11 , take smaller 9
eg 140
140 -> 131 or 141 ; 141 is closer
eg 23 -> 22 or 33, 22 is closer
eg 238 -> 232 or 242, 242 is closer
eg 1238 --> 1221 or 1331 ; 1221 is closer
eg 12385 -> 12321 or 12221 or 12421, 12421 is closer

so we're seeing that we have to change lhs to get the greater, rhs to get the smaller
and when you change the rhs ofc you're affecting the middle value as well
oh thats not true 140 -> 141 is increasing vs 131 
hmm doesnt address the edge cases when you're near a boundary like
101 -> 99? or 10 to 9 vs 11

hmm the hint says "how many different cases are possible?" 
so i mean yes its true that common palindromes are shared right
like for 1221 -> the closest larger is 1331 and closest smaller is 1111
so sure if anything is between 1111 and 1221, take the middle and its the closer one
and same for 1221 and 1331 

1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 111 121 131 141 151 161 171 181 191 
202 212 222 232 242 252 262 272 282 292 303 313 323... 989 999 1001 1111 1221 1331
1441 1551 1661 1771 1881 1991 2002 2112 2222 2332 2442 .. 9889 9999 10001 10101 10201
10301 10401 10501 ... 10901 11011 11111 11211 .... 99899 99999 100001 101101 ... 

what I'm basically doing is taking the mid = (number of digits - 1) // 2 and if ts odd then I reverse
the 0 : mid - 1 from mid + 1: ; and if its even I take 0 : mid from mid + 1: 
and the 0: mid - 1 is incremented by a unit value each turn thats basically all im doing here
so for 1 digit: 9 ; 2 digits : 9; 3 digits: 99; 4 digits : 99, 5 digits: 999 etc 
so at 18 digits I have 9 9s and everything before it lolz 

yeah so ignoring the edge cases when you need to cnsider candidates less or more than the current
number of digits
we can just take mid = (lenght - 1) // 2
if even -> closest palindrome is 0:mid + 0:mid[::-1] or decrement 0 : mid or increment 0 : mid
if odd -> its 0 : mid - 1 + mid + 0:mid - 1 [::-1] and decement mid or increment mid 

now we have edge cases where we have decrement / increment that reaches the next length

102 -> 1 + 0 + 1 = 101; increment: 1 + 1 + 1 = 111; decrement 

I suppose we could take them as edge cases 
the max is always 9 * length
so take (length - 1) * 9 

the min? 1 + (len - 2) * 0 + 1
thats O(N) O(N) O(N) space since we are doing string concats and conversions
and N is in the order of str

oh you could also chec kif this palidnrome == all 9s or 10001 etc then you know
the next decrement or increment is a min or max value
'''
class Solution:
    def nearestPalindromic(self, n: str) -> str:
        if len(n) == 1: return str(int(n) - 1)

        length = len(n)
        mid = (length - 1) // 2
        lhs = n[0 : mid + 1] if length % 2 == 0 else n[0 : mid]

        #get this palindrome
        if length % 2 == 0:
            this_palindrome = lhs + lhs[::-1]
        else:
            this_palindrome = lhs + n[mid : mid + 1] + lhs[::-1]

        #get smaller palindrome
        if length % 2 == 0:
            smaller_lhs = str(int(lhs) - 1)
            if len(smaller_lhs) < len(lhs) or smaller_lhs == '0':
                smaller_palindrome = '9' * (length - 1)
            else:
                smaller_palindrome = smaller_lhs + smaller_lhs[::-1]

        else:
            smaller_lhs = str(int(lhs + n[mid : mid + 1]) - 1)
            if len(smaller_lhs) < len(str(int(lhs + n[mid : mid + 1]))):
                smaller_palindrome = '9' * (length - 1)
            else:
                smaller_palindrome = smaller_lhs[0:-1] + smaller_lhs[-1:] + smaller_lhs[0:-1][::-1]

        #get larger palindrome
        if length % 2 == 0:
            larger_lhs = str(int(lhs) + 1)
            if len(larger_lhs) > len(lhs):
                larger_palindrome = '1' + (length - 1) * '0' + '1'
            else:
                larger_palindrome = larger_lhs + larger_lhs[::-1]

        else:
            larger_lhs = str(int(lhs + n[mid : mid + 1]) + 1)
            if len(larger_lhs) > len(lhs) + 1: #odd lhs excludes middle val
                larger_palindrome = '1' + (length - 1) * '0' + '1'
            else:
                larger_palindrome = larger_lhs[0:-1] + larger_lhs[-1:] + larger_lhs[0:-1][::-1]

        this_distance = abs(int(this_palindrome) - int(n))
        if this_distance == 0: this_distance = inf #cant return self if self is palindrome
        smaller_distance = abs(int(smaller_palindrome) - int(n))
        larger_distance = abs(int(larger_palindrome) - int(n))
        min_distance = min(this_distance, smaller_distance, larger_distance)


        if smaller_distance == min_distance:
            return smaller_palindrome
        elif this_distance == min_distance:
            return this_palindrome
        else:
            return larger_palindrome
16100