<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>

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        length = len(n)
        candidates = set()
        
        # Edge cases: for n = "1", nearest palindrome is "0".
        if n == "1":
            return "0"
        
        # 1. Consider the smallest palindrome larger than n by adding 1 to the first half and mirroring it.
        # 2. Consider the largest palindrome smaller than n by subtracting 1 from the first half and mirroring it.
        # 3. Consider direct mirroring of the first half to create a potential palindrome.
        
        # Create the basic middle palindrome by mirroring the first half
        prefix = n[:(length + 1) // 2]
        prefix_number = int(prefix)
        
        # Generate the candidates
        for i in [-1, 0, 1]:
            # Adjust the prefix and create the palindrome
            new_prefix = str(prefix_number + i)
            if length % 2 == 0:
                candidate = new_prefix + new_prefix[::-1]
            else:
                candidate = new_prefix + new_prefix[:-1][::-1]
            candidates.add(candidate)
        
        # Adding edge cases: smallest palindrome larger than current number of digits, and largest palindrome smaller
        # than the current number of digits
        candidates.add(str(10**(length-1) - 1))
        candidates.add(str(10**length + 1))
        
        # Remove the original number from the candidates set
        candidates.discard(n)
        
        # Find the closest palindrome by comparing the absolute difference
        closest_palindrome = min(candidates, key=lambda x: (abs(int(x) - int(n)), int(x)))
        
        return closest_palindrome
16200