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

// Author: PrintulVostru
class Solution {
public:
    string nearestPalindromic(string n) {
        int lengthOfN = n.size();
        if (lengthOfN == 1)
            return to_string(stoi(n) - 1);

        string decrementString = n;
        for (int i = (lengthOfN + 1) / 2; i < lengthOfN; i++)
            decrementString[i] = '0';
        int64 decrementNumber = stoll(decrementString) - 1;
        string decrementPalindrome = constructPalindromeFromHalf(to_string(decrementNumber));

        string incrementString = n;
        for (int i = (lengthOfN + 1) / 2; i < lengthOfN; i++)
            incrementString[i] = '9';
        int64 incrementNumber = stoll(incrementString) + 1;
        string incrementPalindrome = constructPalindromeFromHalf(to_string(incrementNumber));
        
        string half = constructPalindromeFromHalf(n);
        string closestPalindrome = decrementPalindrome;
        closestPalindrome = getBestString(n, closestPalindrome, half);
        closestPalindrome = getBestString(n, closestPalindrome, incrementPalindrome);
        return closestPalindrome;
    }

private:
    typedef long long int64;

    string getBestString(string n, string currentBest, string candidate) {
        int64 candidateDistance = getDistanceToN(n, candidate);
        int64 currentDistance = getDistanceToN(n, currentBest);
        if (candidateDistance < currentDistance)
            return candidate;
        return currentBest;
    }

    string constructPalindromeFromHalf(string str) {
        string palindrome = str;
        int n = str.size();
        for (int i = (n + 1) / 2, j = n / 2 - 1; i < n; i++, j--)
            palindrome[i] = palindrome[j];
        return palindrome;
    }

    int64 getDistanceToN(string n, string str) {
        int64 valueN = stoll(n);
        int64 valueStr = stoll(str);
        if (valueN == valueStr)
            return 1LL << 62;
        return abs(valueN - valueStr); 
    }
};
9400