564. Find the Closest Palindrome - Detailed Explanation

Problem Statement

Given a string representing a positive integer, find the closest integer (not including the number itself) that is a palindrome. Two numbers are “close” if the absolute difference between them is minimized. If there is a tie, return the smaller one. The result should also be returned as a string.

Example 1

• Input: "123"
• Output: "121"
• Explanation:
  The palindrome "121" is closer to "123" (difference = 2) than "131" (difference = 8).

Example 2

• Input: "1"
• Output: "0"
• Explanation:
  The only palindrome less than 1 is 0.

Example 3

• Input: "99"
• Output: "101"
• Explanation:
  Although "88" is a palindrome, "101" is closer to "99" (difference = 2) than "88" (difference = 11).

Constraints

• The input is a non-negative integer represented as a string.

• The input number does not have leading zeros (except for the number "0" itself).

• The number can be very large, so it should be treated as a string to avoid overflow issues.

Hints

1. Mirroring Technique:
   A palindrome reads the same forward and backward. A natural idea is to take the first half of the digits (and the middle digit if the length is odd) and mirror them to form a candidate palindrome.

2. Adjusting the Prefix:
   The straightforward mirror of the input might yield the same number. To get nearby palindromes, consider:

   • Decreasing the first half (or prefix) by one.
   • Increasing the first half by one.

   Then mirror these adjusted prefixes to form new candidates.

3. Edge Cases – Different Lengths:
   Also consider palindromes that result from changing the length of the number:

   • A palindrome with one fewer digit (e.g., for "1000", consider "999").
   • A palindrome with one more digit (e.g., for "999", consider "1001").

Approach Overview

The key idea is to generate a set of candidate palindromes and then pick the one that is closest to the input number (excluding the number itself).

Steps:

1. Extract the Prefix:
   Let n be the length of the input string.

   • For odd n, take the first (n + 1) / 2 digits.
   • For even n, take the first n / 2 digits.

2. Generate Candidates by Mirroring:

   • Candidate A: Direct mirror of the prefix.
   • Candidate B: Mirror of (prefix − 1).
   • Candidate C: Mirror of (prefix + 1).

3. Additional Edge Candidates:

   • Candidate D: The largest number with one fewer digit (e.g., "99", "999", etc.).
   • Candidate E: The smallest number with one more digit (e.g., "1001" for input "999").

4. Exclude the Input Itself:
   Remove the candidate that is exactly equal to the input number.

5. Select the Best Candidate:
   Compare the absolute difference between the input number and each candidate. In case of ties, select the candidate with the smaller numerical value.

Detailed Walkthrough

Consider the input "12345":

1. Prefix Extraction:

   • Length is 5 (odd). Take the first 3 digits: "123".

2. Generate Basic Candidate:

   • Mirror "123" to form "12321".

3. Generate Adjusted Candidates:

   • Decrement prefix: "123" → "122" → Mirror to get "12221".
   • Increment prefix: "123" → "124" → Mirror to get "12421".

4. Generate Edge Candidates:

   • The largest palindrome with one fewer digit: For a 5-digit number, this candidate is "9999".
   • The smallest palindrome with one more digit: For a 5-digit number, this candidate is "100001".

5. Candidate List:
   Remove any candidate equal to the original number (if present). Then, compute the absolute difference from the input for each candidate:

   • "12321"
   • "12221"
   • "12421"
   • "9999"
   • "100001"

6. Choosing the Closest:
   Compare the differences between each candidate and "12345" and pick the one with the smallest difference. If two candidates have the same difference, return the numerically smaller one.

Code Implementation

Python Code