Tìm palindrome gần nhất (Find the Closest Palindrome) trong C++

Cho số n (dạng chuỗi). Tìm palindrome gần nhất (khác n), ưu tiên hiệu nhỏ hơn, tie-break lấy số nhỏ hơn.

Ví dụ

"145" → "141".

Ý tưởng

Palindrome gần nhất chỉ khác ở nửa đầu. Sinh ứng viên từ: nửa đầu, nửa đầu±1, và các trường hợp biên (999..., 100...001). So sánh tất cả ứng viên.

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string nearestPalindromic(string n) {
        int len = n.size();
        if(len==1) return string(1, --n[0]);
        long halfLen = (len+1)/2;
        long halfVal = stol(n.substr(0, halfLen));
        vector<long> cand = {
            (long)pow(10,len)-1, (long)pow(10,len-1)-1,
            (long)pow(10,len-1)+1, (long)pow(10,len)+1
        };
        for(long hv : {halfVal, halfVal-1, halfVal+1}) {
            string s = to_string(hv);
            string rev = s;
            if(len%2) rev.pop_back();
            reverse(rev.begin(), rev.end());
            cand.push_back(stol(s+rev));
        }
        sort(cand.begin(), cand.end());
        long val = stol(n), bestDiff = LLONG_MAX;
        string ans;
        for(long c : cand) {
            if(c==val) continue;
            long diff = labs(c-val);
            if(diff < bestDiff) { bestDiff=diff; ans=to_string(c); }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.nearestPalindromic("145"); // 141
    return 0;
}