<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 {
public:
    string nearestPalindromic(string n) {
        int len = n.size();
        string prefix = n.substr(0, (len+1)/2);
        long long prefix_num = stoll(prefix);
        vector<string> cand(5);
        cand[0] = string(len-1, '9');
        cand[1] = build_palindrome(to_string(prefix_num+1), len);
        cand[2] = build_palindrome(to_string(prefix_num-1), len);
        cand[3] = build_palindrome(prefix, len);
        cand[4] = string(len, '0');
        cand[4][0] = cand[4][len-1] = '1';
        sort(cand.begin()+1, cand.end());
        long long min_diff = LONG_LONG_MAX;
        int min_idx;
        long long num = stoll(n);
        for (int i=0; i<5; ++i) {
            if (cand[i].length()==0) continue;
            long long num_cand = stoll(cand[i]);
            if (num_cand==num) continue;
            long long diff = abs(num-num_cand);
            if (diff<min_diff) {
                min_diff = diff;
                min_idx = i;
            }
        }
        return cand[min_idx];
    }
private:
    string build_palindrome(string prefix, int len) {
        if (prefix.length()>len) prefix.pop_back();
        for (int i=len/2-1; i>=0; --i) prefix.push_back(prefix[i]);
        return prefix;
    }
};
8700