<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 bigger_string(string s1, string s2) {
        if(s1.size() > s2.size()) return s1;
        if(s2.size() > s1.size()) return s2;
        for(int i = 0; i < s1.size(); i++) {
            if(s1[i] > s2[i]) return s1;
            if(s2[i] > s1[i]) return s2; 
        }
        return s1;
    }
    string string_diff(string s1, string s2) {
        if(bigger_string(s1, s2) == s2) {
            string temp = s1;
            s1 = s2;
            s2 = temp;
        }
        string res = "";
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        int carry = 0;
        for(int i = 0; i < s1.size(); i++) {
            char s2_val = i < s2.size()? s2[i] : '0';
            if(s1[i] >= s2_val + carry) {
                res+=(s1[i] - s2_val - carry + '0');
                carry = 0;
            }
            else {
                res+=(s1[i] + 10 - s2_val - carry + '0');
                carry = 1;
            }
        }
        while(res.size() && res.back() == '0') {
            res.pop_back();
        }
        reverse(res.begin(), res.end());
        return res;
    }

    string addStrings(string s1, string s2) {
        bool carry = false;
        string ans = "";

        int p1 = s1.size() - 1;
        int p2 = s2.size() - 1;

        while(p1 >= 0 || p2 >= 0) {
            int d1 = (p1 >= 0)? s1[p1]-'0' : 0;
            int d2 = (p2 >= 0)? s2[p2]-'0' : 0;

            int sum = d1 + d2 + carry;

            carry = (sum >= 10);

            ans.push_back(sum%10+'0');

            p1--;
            p2--;
        }

        if(carry) {
            ans.push_back('1');
        }
        
        reverse(ans.begin(), ans.end());

        return ans;
    }

    string nearestPalindromic(string n) {
        vector<string> candidates;
        candidates.push_back("1" + string(n.size()-1, '0') + "1");
        if(n.size() > 1) candidates.push_back(string(n.size()-1, '9'));
    
        string half_string = n.substr(0, n.size()/2);
        // cout << half_string << endl;

        if(n.size() % 2 == 0) {
            string temp = half_string;
            string reversed_temp = temp;
            reverse(reversed_temp.begin(), reversed_temp.end());
            candidates.push_back(temp + reversed_temp);

            temp = string_diff(half_string, "1");
            reversed_temp = temp;
            reverse(reversed_temp.begin(), reversed_temp.end());
            candidates.push_back(temp + reversed_temp);

            temp = addStrings(half_string, "1");
            reversed_temp = temp;
            reverse(reversed_temp.begin(), reversed_temp.end());
            candidates.push_back(temp + reversed_temp);
        }
        else {
            string temp = half_string;
            string reversed_temp = temp;
            reverse(reversed_temp.begin(), reversed_temp.end());
            for(int i = -1; i <= 1; i++) {
                char middle_chr = n[n.size()/2];
                if(middle_chr == '0' && i == -1) continue;
                if(middle_chr == '9' && i == 1) continue;
                middle_chr+=i;
                candidates.push_back(temp + middle_chr + reversed_temp);
            }
        }

        string min_diff = string(n.size(), '9');
        string res = string(n.size(), '9');

        // for(string s: candidates) {
        //     cout << s << endl;
        // }

        for(string s: candidates) {
            string diff = string_diff(n, s);
            // cout << s << " " << diff << endl;
            if(s == n) continue;
            if(bigger_string(diff, min_diff) != diff) {
                res = s;
                min_diff = diff;
            }
            else if(bigger_string(diff, min_diff) == min_diff && bigger_string(s, res) == res) {
                res = s;
            }
        }

        return res;
    }
};
10900