Find the Closest Palindrome

String, Math

Hard

Given an integer n, find the closest integer (not including itself), which is a palindrome.

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

Example 1:

Input:
 "123"

Output:
 "121"

Note:

1. The input n is a positive integer represented by string, whose length will not exceed 18.

2. If there is a tie, return the smaller one as answer.

Solution

Based on: @fun4LeetCode's answer:

https://leetcode.com/problems/find-the-closest-palindrome/discuss/102389/Java-solution-with-detailed-proof

8 ms, faster than 98.75%

3 steps:

I -- The given number itself is a palindrome

II -- The given number is a not palindrome

III -- Construct the whole palindrome from its left part

Construct a palindrome based on left half, then find the nearest palindrome larger or smaller than curP: nextP, prevP. Then compare the diff between num, cur, prev, next.

class Solution {
    public String nearestPalindromic(String n) {
        if (n == null || n.isEmpty()) {
            return "";
        }
        char[] p = n.toCharArray();
        for (int i = 0, j = p.length - 1; i < j; i++, j--) {
            p[j] = p[i];
        }

        String curP = String.valueOf(p);
        String prevP = nearestPalindromeOf(curP, false);
        String nextP = nearestPalindromeOf(curP, true);

        long num = Long.valueOf(n);
        long cur = Long.valueOf(curP);
        long prev = Long.valueOf(prevP);
        long next = Long.valueOf(nextP);

        long d1 = Math.abs(num - cur);
        long d2 = Math.abs(num - prev);
        long d3 = Math.abs(num - next);

        if (num == cur) {
            return d2 <= d3 ? prevP : nextP;
        } else if (num > cur) {
            return d1 <= d3 ? curP : nextP;
        } else {
            return d2 <= d1 ? prevP : curP;
        }
    }

    /**
    * @param s - input palindrome string
    * @param dir true if finding larger, false if finding smaller
    * @return nearest palindrome string of input palindrome
    */
    public String nearestPalindromeOf(String s, boolean dir) {
        int len = s.length();
        int k = len / 2;
        // make sure left include the mid point if len is odd number
        int base = Integer.valueOf(s.substring(0, len - k)); 
        base += dir ? 1 : -1;

        // handle "11", "1" case
        if (base == 0) {
            if (k == 0) {
                return "0";
            }
            return "9";
        }

        StringBuilder left = new StringBuilder(String.valueOf(base));
        StringBuilder right = new StringBuilder(left).reverse();
        // handle "1001", "10001" type of case
        if (k > left.length()) {
            right.append("9");
        }

        return left.append(right.substring(right.length() - k)).toString();
    }

}

LeetCode official

Using Math:

• Time complexity : O(l). Scanning, insertion, deletion,, mirroring takes O(l), wherellis the length of the string.

• Space complexity : O(l). Temporary variables are used to store the strings.

public class Solution {
    public String mirroring(String s) {
        String x = s.substring(0, (s.length()) / 2);
        return x + (s.length() % 2 == 1 ? s.charAt(s.length() / 2) : "") + new StringBuilder(x).reverse().toString();
    }
    public String nearestPalindromic(String n) {
        if (n.equals("1"))
            return "0";

        String a = mirroring(n);
        long diff1 = Long.MAX_VALUE;
        diff1 = Math.abs(Long.parseLong(n) - Long.parseLong(a));
        if (diff1 == 0)
            diff1 = Long.MAX_VALUE;

        StringBuilder s = new StringBuilder(n);
        int i = (s.length() - 1) / 2;
        while (i >= 0 && s.charAt(i) == '0') {
            s.replace(i, i + 1, "9");
            i--;
        }
        if (i == 0 && s.charAt(i) == '1') {
            s.delete(0, 1);
            int mid = (s.length() - 1) / 2;
            s.replace(mid, mid + 1, "9");
        } else
            s.replace(i, i + 1, "" + (char)(s.charAt(i) - 1));
        String b = mirroring(s.toString());
        long diff2 = Math.abs(Long.parseLong(n) - Long.parseLong(b));


        s = new StringBuilder(n);
        i = (s.length() - 1) / 2;
        while (i >= 0 && s.charAt(i) == '9') {
            s.replace(i, i + 1, "0");
            i--;
        }
        if (i < 0) {
            s.insert(0, "1");
        } else
            s.replace(i, i + 1, "" + (char)(s.charAt(i) + 1));
        String c = mirroring(s.toString());
        long diff3 = Math.abs(Long.parseLong(n) - Long.parseLong(c));

        if (diff2 <= diff1 && diff2 <= diff3)
            return b;
        if (diff1 <= diff3 && diff1 <= diff2)
            return a;
        else
            return c;
    }
}

Reference

https://leetcode.com/problems/find-the-closest-palindrome/solution/