<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 {
    long generatePalidromic(long first_half, bool even) {
        long res = first_half;
        if (!even) {
            first_half /= 10;
        }
        while (first_half > 0) {
            res = res * 10 + first_half % 10;
            first_half /= 10;
        }
        return res;
    }

public:
    string nearestPalindromic(string n) {
        // mirror the first half
        // mirror the first half - 1
        // mirror the first half + 1
        // n = 9, 99, 999, ...
        // n = 1001, 101, ...

        int len = n.length();
        bool even = len % 2 == 0;
        int mid = even ? len / 2 - 1 : len / 2;
        long first_half = stol(n.substr(0, mid + 1));

        vector<long> candidates;
        candidates.push_back(generatePalidromic(first_half, even));
        candidates.push_back(generatePalidromic(first_half + 1, even));
        candidates.push_back(generatePalidromic(first_half - 1, even));
        candidates.push_back(long(pow(10, len)) + 1);
        candidates.push_back(long(pow(10, len - 1)) - 1);

        long diff = LONG_MAX;
        long res = 0;
        long num = stol(n);
        for (long cand : candidates) {
            if (cand == num) {
                continue;
            }
            if (abs(cand - num) < diff) {
                res = cand;
                diff = abs(cand - num);
            } else if (abs(cand - num) == diff) {
                res = min(res, cand);
            }
        }
        return to_string(res);
    }
};
8200