Leetcode 564: Find the Closest Palindrome

Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers.

Example 1:

Input: n = "123"
Output: "121"

Example 2:

Input: n = "1"
Output: "0"
Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.

Constraints:

• 1 <= n.length <= 18
• n consists of only digits.
• n does not have leading zeros.
• n is representing an integer in the range [1, 1018 - 1]

Problem Analysis:

Assume n is “123456”, so half of string n is “123”, the closest palindrome is “123321”, if n is “123321”, the half of string n is “123”, but “123321” is equal n, so we can choose “124421” and “122221”, the two is same distance to the “123321”, so we should choose the smaller one “122221”. If n is “123211”, the half of string is “123”, the closest palindrome is “122221”.

So we conclude this: we can first get half of string n, assume it is number abc, then we use abc, or add 1, or minus 1, combine with reversing of the number. The closest palindrome is one of them. If string n is odd length, it is similar.

But there are some corner cases we should notice. if string n is length of 1, then the closest palindrome is number of n minus 1, unless n is “0”, then the closest palindrome is “1”.

If string n is the pattern of “10”, “100”, …, “1000000”, then the closest palindrome is the number n minus 1.

If string n is the pattern of “11”, “101”, …, “1000001”, then the closest palindrome is the number n minus 2.

If string n is the pattern of “99”, “999”, …, “9999999”, then the closest palindrome is the number n + 2.

Solution

class Solution {
public:
    string nearestPalindromic(string n) {
        if (n.size() == 1) {
            if (n[0] == '0') return "1";
            --n[0];
            return n;
        }
        if (is10x(n) || is1x1(n)) 
            return string(n.size() - 1, '9');
        else if (is9x(n))
            return "1" + string(n.size() - 1, '0') + "1";
        int half = (n.size() & 1) ? stoll(n.substr(0, n.size() / 2 + 1)) : stoll(n.substr(0, n.size() / 2));
        long long great = 
            stoll(to_string(half + 1) + getReverse(to_string(half + 1), n.size() & 1));
        long long small = 
            stoll(to_string(half - 1) + getReverse(to_string(half - 1), n.size() & 1));
        long long equal = 
            stoll(to_string(half) + getReverse(to_string(half), n.size() & 1));
        long long minDiff{LLONG_MAX};
        long long res;
        if (stoll(n) - small < minDiff) {
            minDiff = stoll(n) - small;
            res = small;
        }
        if (stoll(n) != equal && abs(stoll(n) - equal) < minDiff) {
            minDiff = abs(stoll(n) - equal);
            res = equal;
        }
        if (great - stoll(n) < minDiff) {
            minDiff = great - stoll(n);
            res = great;
        }
        return to_string(res);
    }
    string getReverse(string s, bool odd) {
        if (odd) s.pop_back();
        for (int i = 0, j = s.size() - 1; i < j; ++i, --j)
            swap(s[i], s[j]);
        return s;
    }
    bool is10x(const string& n) {
        if (n[0] != '1') return false;
        for (int i = 1; i < n.size(); ++i) {
            if (n[i] != '0') return false;
        }
        return true;
    }
    bool is1x1(const string& n) {
        if (n[0] != '1' || n[n.size() - 1] != '1') 
            return false;
        
        for (int i = 1; i < n.size() - 1; ++i) {
            if (n[i] != '0') return false;
        }
        return true;
    }
    bool is9x(const string& n) {
        for (int i = 0; i < n.size(); ++i) {
            if (n[i] != '9') return false;
        }
        return true;
    }
};

time complexity is O(1)

Space complexity is O(1)