<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 {
private:
    bool is_palindrome(const string& n) const {
        if (n.size() == 1) return true;

        const size_t cap = n.size() / 2;
        for (size_t idx = 0; idx < cap; ++idx) {
            if (n[idx] != n[n.size() - 1 - idx]) {
                return false;
            }
        }
        return true;
    }

    string make_modified_prefix(const string& base, const int64_t midpoint, const int64_t delta) const {
        string res = base.substr(0, midpoint);

        // special case exists here for even numbers where midpoint digit is > 0
        // if (base.size() % 2 == 0) {
            // res 

            // if (delta < 0 && res.back() > '0') {
            //     res.back() -= 1;
            // }
            // else if (delta > 0 && res.back() < '9') {
            //     res.back() += 1;
            // }
        // }

        return std::to_string(std::stoll(res) + delta);

        // return res;
    }

    string expand_palindrome(const string& prefix, const int64_t midpoint, const bool is_odd_expansion) const {
        string ideal_pali = prefix;
        for (int64_t idx = prefix.size() - 1; idx >= 0; --idx) {
            if (idx == prefix.size() - 1 && is_odd_expansion && prefix.size() == midpoint) continue;
            // cout << "idx: " << idx << endl;
            ideal_pali += prefix[idx];
        }
        return ideal_pali;
    }
public:
    string nearestPalindromic(string n) {
        // some notes:
        // - for single digits, answer is n-1
        // - for double digits, answer is nearest multiple of 11

        const int64_t num = std::stoll(n);
        if (n.size() == 1) return std::to_string(num - 1);

        // more generally, the first half of the digits are fixed, as otherwise we won't be nearest
        // realistically can brute-force since max value is only 10^9

        // integer division rounding down
        // const size_t midpoint = (n.size() - 1) / 3;
        // const string prefix = n.substr(0, midpoint);
        // // cout << prefix << endl;
        // string baseline_str = prefix;
        // while (baseline_str.size() < n.size()) {
        //     baseline_str += "0";
        // }
        // const size_t baseline = std::stoi(baseline_str);
        // string endpoint_str = prefix;
        // while (endpoint_str.size() < n.size() + 1) {
        //     endpoint_str += "9";
        // }
        // const size_t endpoint = std::stoi(endpoint_str);

        // // cout << baseline << " -> " << endpoint << endl;

        // int64_t best = num * 10;
        // for (int64_t idx = baseline; idx < endpoint; ++idx) {
        //     if (idx == num) continue;

        //     const string candidate = std::to_string(idx);
        //     if (this->is_palindrome(candidate)) {
        //         const int64_t delta_new = abs(num - idx);
        //         const int64_t delta_old = abs(num - best);
        //         if (delta_new < delta_old) {
        //             best = idx;
        //         } else if (idx > num) {
        //             // if we found the next palindrome after num and the delta is bigger, we can stop
        //             break;
        //         }
        //     }
        // }

        // optimization: for large enough numbers, the closest palindrome is one we generate
        const size_t midpoint = (n.size() + 1) / 2;
        
        // cout << prefix << endl;
        // cout << ideal_pali << endl;

        // 6 is arbitrarily chosen but gives good perf
        if (midpoint > 5) {
            const string prefix = n.substr(0, midpoint);
            const string prefix_lower = make_modified_prefix(n, midpoint, -1);
            const string prefix_upper = make_modified_prefix(n, midpoint, 1);

            // cout << "p_ " <<  prefix << endl;
            // cout << "pl " <<  prefix_lower << endl;
            // cout << "pu " <<  prefix_upper << endl;

            const bool is_odd_expansion = (n.size() % 2 == 1);

            const string pali_ideal = this->expand_palindrome(prefix, midpoint, is_odd_expansion);
            const string pali_lower = this->expand_palindrome(prefix_lower, midpoint, is_odd_expansion);
            const string pali_upper = this->expand_palindrome(prefix_upper, midpoint, is_odd_expansion);

            if (pali_lower == pali_ideal && pali_ideal == pali_upper) return pali_ideal;

            int64_t best = 0;
            vector<string> candidates = {pali_lower, pali_ideal, pali_upper};
            for (const auto& cand_str : candidates) {
                const int64_t cand = std::stoll(cand_str);

                if (cand == num) continue;

                // cout << "considering " << cand << endl;
                const int64_t delta_new = abs(num - cand);
                const int64_t delta_old = abs(num - best);
                // cout << "old " << delta_old << " -> new " << delta_new << endl;
                if (delta_new < delta_old) {
                    best = cand;
                }
            }
            return std::to_string(best);

            // special case exists here for even numbers where midpoint digit is > 0
            // if (n.size() % 2 == 0) {
            //     if (lower_prefix.back() > '0') {
            //         lower_prefix.back() -= 1;
            //     } else {
            //         lower_prefix.back() += 1;
            //     }
            // }

            // string ideal_pali = prefix;
            // for (int64_t idx = prefix.size() - 1; idx >= 0; --idx) {
            //     if (idx == prefix.size() - 1 && n.size() % 2 == 1) continue;
            //     // cout << "idx: " << idx << endl;
            //     ideal_pali += prefix[idx];
            // }

            // if (prefix == lower_prefix) return ideal_pali;

            // string lower_ideal_pali = lower_prefix;
            // for (int64_t idx = lower_prefix.size() - 1; idx >= 0; --idx) {
            //     if (idx == lower_prefix.size() - 1 && n.size() % 2 == 1) continue;
            //     // cout << "idx: " << idx << endl;
            //     lower_ideal_pali += lower_prefix[idx];
            // }

            // const int64_t lower_ideal_pali_numeric = std::stoll(lower_ideal_pali);
            // const int64_t ideal_pali_numeric = std::stoll(ideal_pali);

            // cout << lower_ideal_pali_numeric << " vs " << ideal_pali_numeric << endl;

            // return abs(num - lower_ideal_pali_numeric) < abs(num - ideal_pali_numeric) ? lower_ideal_pali : ideal_pali;
        } 

        // Circle search

        int64_t best = 0;
        int64_t offset = 1;

        bool found_lesser_pali = false;
        bool found_greater_pali = false;

        vector<int64_t> signs {-1, 1};
        for (int64_t offset = 1; offset < num; ++offset) {
            for (const int64_t sign : signs) {
                const int64_t idx = num + (offset * sign);
                // cout << "considering " << idx << endl;
                const string candidate = std::to_string(idx);
                if (this->is_palindrome(candidate)) {

                    // If we ever find two palindromes on the same side, we've definitely found the closest already
                    if (idx < num) {
                        if (found_lesser_pali) return std::to_string(best);
                        found_lesser_pali = true;
                    }
                    if (idx > num) {
                        if (found_greater_pali) return std::to_string(best);
                        found_greater_pali = true;
                    }

                    const int64_t delta_new = abs(num - idx);
                    const int64_t delta_old = abs(num - best);
                    if (delta_new < delta_old) {
                        best = idx;
                    } else if (idx > num) {
                        // if we found the next palindrome after num and the delta is bigger, we can stop
                        return std::to_string(best);
                    }
                }
            }
        }

        // failure case - should not hit this
        return n;
    }
};

10500