<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 length = n.size();
        set<string> candidates;
        if (n == "1") return "0";
        string prefix = n.substr(0, (length + 1) / 2);
        long long prefixNumber = stoll(prefix);
        for (long long i : {-1, 0, 1}) {
            string newPrefix = to_string(prefixNumber + i);
            string candidate;
            if (length % 2 == 0) {
                candidate = newPrefix + string(newPrefix.rbegin(), newPrefix.rend());
            } else {
                candidate = newPrefix + string(newPrefix.rbegin() + 1, newPrefix.rend());
            }
            candidates.insert(candidate);
        }
        candidates.insert(to_string(static_cast<long long>(pow(10, length - 1)) - 1));
        candidates.insert(to_string(static_cast<long long>(pow(10, length)) + 1));
        candidates.erase(n);
        string closestPalindrome;
        long long minDifference = LLONG_MAX;
        long long num = stoll(n);
        for (const string& candidate : candidates) {
            long long candidateNum = stoll(candidate);
            long long difference = abs(candidateNum - num);
            if (difference < minDifference || (difference == minDifference && candidateNum < stoll(closestPalindrome))) {
                minDifference = difference;
                closestPalindrome = candidate;
            }
        }

        return closestPalindrome;
    }
};
9600