/*
* @lc app=leetcode id=564 lang=cpp
*
* [564] Find the Closest Palindrome
*/
// @lc code=start
class Solution {
public:
string nearestPalindromic(string n) {
const int L = n.size();
unordered_set<long> candidates;
// 多一位数字,10...01
candidates.insert(pow(10, L) + 1);
// 少一位数字,99...99或0
candidates.insert(pow(10, L - 1) - 1);
// prefix + Mid + reverse(prefix)
// Mid = {mid -1, mid, mid + 1}
long prefix = stol(n.substr(0, (L + 1) / 2));
for (long i = -1; i <= 1; ++i) {
string p = to_string(prefix + i);
string pp = p + string(p.rbegin() + (L & 1), p.rend());
candidates.insert(stol(pp));
}
long num = stol(n), min_diff = LONG_MAX, res = 0;
candidates.erase(num);
for (auto c : candidates) {
long diff = abs(c - num);
if (diff < min_diff) {
res = c;
min_diff = diff;
} else if (diff == min_diff) {
res = min(res, c);
}
}
return to_string(res);
}
};
// @lc code=end