Find the Closest Palindrome

Problem Description

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.

Key Insights

• A palindrome reads the same forwards and backwards.
• The closest palindrome can be generated based on the original number by manipulating its digits.
• Consider edge cases such as numbers with a single digit and large numbers close to powers of ten.
• Generate potential palindrome candidates by altering the first half of the number and mirroring it.

Space and Time Complexity

Time Complexity: O(k), where k is the number of digits in n (up to 18). Space Complexity: O(1), as we are only using a constant amount of space for variables.

Solution

To find the closest palindrome to a given number represented as a string, we can generate several candidate palindromes by manipulating the first half of the string. The algorithm proceeds as follows:

1. Create potential palindrome candidates based on the first half of the number.
2. Include edge cases like one less than and one more than the current number.
3. Compare the absolute differences of these candidates with the original number to find the closest palindrome.
4. If two candidates are equally close, return the smaller one.

The solution employs string manipulation to create and check palindrome candidates.

Code Solutions