Find the Closest Palindrome

This approach involves converting the input string n to a number and then iteratively checking numbers smaller and larger than n until a palindrome is found in each direction. The one with the smaller absolute difference to n is the answer.

• Convert the input string n to a long variable num.
• Find the first palindrome smaller than num:
  • Initialize lower = num - 1.
  • Loop downwards from lower, checking if each number is a palindrome.
  • A number is checked by converting it to a string and verifying if the string is the same forwards and backward.
  • Stop when the first smaller palindrome is found.
• Find the first palindrome larger than num:
  • Initialize upper = num + 1.
  • Loop upwards from upper, checking if each number is a palindrome.
  • Stop when the first larger palindrome is found.
• Compare the absolute differences: |num - lower| and |upper - num|.
• If |num - lower| is less than or equal to |upper - num|, return lower. Otherwise, return upper.
• Convert the result back to a string.

The brute-force method is the most straightforward way to conceptualize the problem. The core idea is to search outwards from the given number n in both directions (decreasing and increasing) and stop at the very first palindrome encountered on each side.

1. Conversion: The input string n is first converted into its numerical representation (e.g., a long in Java) to allow for arithmetic operations.
2. Downward Search: We start a search for the largest palindrome that is smaller than n. This is done by initializing a variable lower to n - 1 and decrementing it in a loop. In each iteration, we check if lower is a palindrome. The first number that satisfies this condition is our first candidate.
3. Upward Search: Similarly, we search for the smallest palindrome that is larger than n. We initialize upper to n + 1 and increment it until we find a palindrome.
4. Comparison: After finding both lower and upper palindromes, we determine which one is closer to n by comparing the absolute differences n - lower and upper - n. According to the problem statement, if the differences are equal (a tie), we must choose the smaller palindrome, which is lower.
5. Result: The chosen number is then converted back to a string and returned.

To check if a number is a palindrome, a helper function is used. It converts the number to a string and checks if the string reads the same forwards and backward, typically by using a two-pointer technique.

class Solution {
    public String nearestPalindromic(String n) {
        long num = Long.parseLong(n);
        long lower = findLowerPalindrome(num - 1);
        long upper = findUpperPalindrome(num + 1);

        long diff1 = num - lower;
        long diff2 = upper - num;

        if (diff1 <= diff2) {
            return String.valueOf(lower);
        } else {
            return String.valueOf(upper);
        }
    }

    private long findLowerPalindrome(long limit) {
        long i = limit;
        while (true) {
            if (isPalindrome(String.valueOf(i))) {
                return i;
            }
            i--;
        }
    }

    private long findUpperPalindrome(long limit) {
        long i = limit;
        while (true) {
            if (isPalindrome(String.valueOf(i))) {
                return i;
            }
            i++;
        }
    }

    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}