<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 {
    bool is_palindrome(string& s)
    {
        int i = 0, j = s.size()-1;
        while (i < j) {
            if (s[i] != s[j]) {
                return false;
            }
            i++;
            j--;
        }

        return true;
    }
    long long get_delta(const string a, const string b)
    {
        //cout << a << " " << b << "\n";
        if (b.empty()) {
            return LONG_MAX;
        }
        long long a1 = stoll(a), a2 = stoll(b);
        //cout << a1 << " " << a2 << "\n";
        return abs(a1 - a2);
    }
    bool big(const string a, const string b)
    {
        if (b.empty()) {
            return true;
        }
        long long a1 = stoll(a), a2 = stoll(b);

        return a1 > a2;
    }
    string func9(int sz) 
    {
        string ans = "";
        while (sz--) {
            ans.push_back('9');
        }

        return ans;
    }
    string func1(int sz) 
    {
        string ans = "1";
        sz -= 2;
        while (sz--) {
            ans.push_back('0');
        }
        ans.push_back('1');
        return ans;
    }
    string func2(string base, int tot_sz)
    {
        int st = (tot_sz - base.size()) - 1;

        while (st >= 0) {
            base.push_back(base[st]);
            st--;
        }

        return base;
    }
public:
    string nearestPalindromic(string n) {
        int i = 0, j = n.size()-1;
        string ans = "";
        string n1 = n;
        long long delta = LONG_MAX, cur_delta = LONG_MAX;
        
        int mid = (n1.size()&1) ? (n1.size()/2)+1 : (n1.size()/2);
        string base = n1;
        while (base.size() > mid) {
            base.pop_back();
        }
        string can1 = func2(base, n1.size());
        vector<string> vec;

        vec.push_back(func2(base, n1.size()));
        long long val = stoll(base);
        vec.push_back(func2(to_string(val+1), n1.size()));
        vec.push_back(func2(to_string(val-1), n1.size()));
        
        //long long cur_delta = get_delta(n1, n);
        string all9 = func9(n1.size()-1);
        string all1 = func1(n1.size()+1);
        vec.push_back(all9);
        vec.push_back(all1);
/*
        delta = get_delta(n1, all9);
        cout << delta << "\n";
        if (delta <= cur_delta) {
            n = all9;
            cur_delta = delta;
        }

        delta = get_delta(n1, all1);
        
        if (delta < cur_delta) {
            n = all1;
            cur_delta = delta;
        }
   
*/
        for (string can1: vec) {
            if (n1 == can1) {
                continue;
            }
            delta = get_delta(n1, can1);
            //cout << can1 << " " << delta << " " << cur_delta << " " << big(n, can1) << "\n";
            if (delta < cur_delta || (delta == cur_delta && big(n, can1))) {
                n = can1;
                cur_delta = delta;
            }
        }
        
        return n;
    }
};
9700