<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) {
        if (n.size() == 1){
            n[0] -= 1;
            return n;
        }
        vector<string> check;
        string nextdig(n.size()+1,'0');
        nextdig[0] = '1';
        nextdig[n.size()] = '1';
        
        string lastdig(n.size()-1,'9');
        

        string mid = "";
        if (n.size() % 2 == 1){
            mid.push_back(n[(n.size())/2]);
        }
        string left_str = n.substr(0,(n.size())/2);
        //std::cout << left_str << " " << mid << std::endl;
        unsigned long long left = stoull(left_str.c_str());
        string cm1 = to_string(left-1);
        string c0 = to_string(left);
        string c1 = to_string(left+1);
        string rcm1 = cm1;
        string rc0 = c0;
        string rc1 = c1;
        reverse(rcm1.begin(), rcm1.end());
        reverse(rc0.begin(), rc0.end());
        reverse(rc1.begin(), rc1.end());
        string temp1 = c0;
        string temp2 = c0;
        if (mid.size() == 0){
            cm1 = cm1 + rcm1;
            c0 = c0 + rc0;
            c1 = c1 + rc1;
        }
        else{
            char x = mid[0];
            cm1.push_back('9');
            cm1 = cm1 + rcm1;
            c0.push_back(x);
            c0 = c0 + rc0;
            c1.push_back('0');
            c1 = c1 + rc1;
        }
        check.push_back(nextdig);
        check.push_back(c1);
        check.push_back(c0);
        if (mid.size() != 0 && mid[0] < '9'){
            char x = mid[0]+1;
            temp1.push_back(x);
            temp1 = temp1 + rc0;
            check.push_back(temp1); 
        }
        if (mid.size() != 0 && mid[0] > '0'){
            char x = mid[0]-1;
            temp2.push_back(x);
            temp2 = temp2 + rc0;
            check.push_back(temp2); 
        }
        
        check.push_back(cm1);
        check.push_back(lastdig);
        string best;
        unsigned long long best_diff = LONG_LONG_MAX;
        unsigned long long n_val = stoull(n.c_str());
        for (string eval:check){
            std::cout << eval << std::endl;
            if (eval[0] == '0') continue;
            unsigned long long eval_val = stoull(eval.c_str());
            unsigned long long diff;
            if (eval_val < n_val){
                diff = n_val - eval_val;
            }
            else{
                diff = eval_val - n_val;
            }
            if (diff != 0 && diff <= best_diff){
                best = eval;
                best_diff = diff;
            }

        }
        return best;
    }
};
9600