<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 helper(int i,int j){
        if(j==0){
            return to_string(i);
        }
        string jj=to_string(j);
        reverse(jj.begin(),jj.end());
        return to_string(i)+jj;
    }
    string nearestPalindromic(string s) {
        int n=s.size();
        if(n==1){
            return to_string(stoi(s)-1);
        }
        vector<string> palindrome;
        string part1="";
        string part2="1";
        for(int i=0;i<n-1;i++){
            part1+="9";
            part2+="0";
        }
        /*
        7464
        9999 999
        1001 10001

        */
        palindrome.push_back(part1);
        palindrome.push_back(part1+"9");
        part2.back()='1';
        palindrome.push_back(part2);
        part2.pop_back();
        palindrome.push_back(part2+"01");
        string half="";
        for(int i=0;i<(n+1)/2;i++){
            half+=s[i];
        } 
        for(long long i=stol(half)-1;i<=(stol(half)+1);i++){
            if(n%2){
                palindrome.push_back(helper(i,i/10));
            }else{
                palindrome.push_back(helper(i,i));
            }
        }
        string ans;
        map<long long,vector<string>> mp;
        for(auto it:palindrome){
            long long diff = abs(stol(it)-stol(s));
            if(diff){
                mp[diff].push_back(it);
            }
        }
        for(auto it:mp){
            string part=mp[it.first][0];
            for(auto itt:it.second){
                if(itt.size()<part.size()){
                    part=itt;
                }else if(itt.size()==part.size()){
                    part=min(part,itt);
                }else{
                    // do nothing
                }
            }
            ans=part;
            break;
        }
        return ans;
    }
};
10800