Leetcode Daily Question 24/08/2024 - 564. 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.

class Solution:
    def closestPalindrome(self, n:str) -> str:
      length = len(n)
      if n == "1":
        return "0"
      
      prefix = n[:(length + 1) // 2]
      prefix_num = int(prefix)
      
      candidates = set()
      
      same_palin = self.makePalin(prefix, length % 2 == 0)
      candidates.add(same_palin)
      
      smaller_palin = self.makePalin(str(prefix_num - 1), length % 2 == 0)
      candidates.add(smaller_palin)
      
      larger_palin = self.makePalin(str(prefix_num + 1), length % 2 == 0)
      candidates.add(larger_palin)
      
      candidates.add(10 ** (length - 1) - 1)
      candidates.add(10 ** length + 1)
      
      candidates.discard(int(n))
      
      closest_palin = min(candidates, key = lambda x: (abs(x - int(n)), x))
      
      return str(closest_palin)
    
    def makePalin(self, componenet: str, is_even_length: bool) -> int:
      if is_even_length:
        return int(component + component[::-1])
      else:
        return int(omponent + component[-2::-1])

Explanation:

This question is quite tricky. However, once we can figure out all the possible cases that n can take, and its associated closest palindrome, we are done.

Here are the important cases to note:
n = "2"
n = "7777"
n = "3003"
n = "33333"
n = "99999"
n = "11011"
n = "45654"
n = "10001"

Let's break it down case by case:

n = "2" - Since any single digit number is naturally palindromic, the closest palindrome is the number 1 less than it. (Since we want the smallest possible to break the tie.)

n = "7777" - This is palindromic of even length. The closest palindrome is "7667" by observation.

n = "3003" - This is palindromic of even length. The closest palindrome is "3113".

n = "99999" - This is palindromic of odd length. The closest palindrome in this case is "1000001" instead of "99899".

n = "11011" - This is palindromic of odd length. The closest palindrome is "11111".

n = "45654"- This is palindromic of odd length. The closest palindrome is "45554"

n = "10001" - This is palindromic of odd length. The closest palindrome is "9999"

We can observe a few things from these cases.

- We just need to use the first half to create our possible candidates for the closest palindrome.

The candidates are
- palindrome created directly from the first half
- palindrome with the "middle"* digit being 1 less or 1 more
- closest repeated "9" palindrome
- closest palindrome that is one more than the closest power of 10 to n.

* - "middle" meaning either the true middle if oddly lengthed, or the two middle values if evenly lengthed.

First let's deal with the single digit numbers.

def closestPalindrome(n):
  length = len(n)
  if int(n) < 10:
    return str(int(n) - 1)

Then we can set up our first half prefix for palindrome construction, and initiate a set to contain all distinct candidates for comparison.

prefix = n[:(length + 1) // 2]
prefix_num = int(prefix)

candidates = set()

Next is constructing the palindromes. We will use a separate function to construct them to make it cleaner. Then we will add these to the comparison set.

same_palin = self.makePalin(prefix, length % 2 == 0)
candidates.add(same_palin)

smaller_palin = self.makePalin(str(prefix_num - 1), length % 2 == 0)
candidates.add(smaller_palin)

larger_palin = self.makePalin(str(prefix_num + 1), length % 2 == 0)
candidates.add(larger_palin)

candidates.add(10 ** (length - 1) - 1) # closest repeated "9"'s palindrome
candidates.add(10 ** length + 1) # closest palindrome that is 1 larger than closest power of 10

candidates.discard(int(n)) # result cannot be the same as n

The result is the candidate with the smallest absolute difference to n and the smallest possible if there is a tie.

closest_palin = min(candidates, key = lambda x: (abs(int(n) - x), x))

return closest_palin

We are left with the makePalin function. This is straightforward.

If n is of odd length, then when constructing the palindrome, we should skip the last character of the prefix when adding on the reversed component, as we only need one middle value.

If n is of even length, then we just tag on the reversed prefix to create our palindrome.

def makePalin(component, is_even_length):
  if is_even_length:
    return component + component[::-1]
  else:
    return component + component[-2::-1]

The time complexity is O(log(n)). The prefix is obtained in O(log(n)) time, the rest of the operations are done in constant time.

The space complexity is O(log(n)). The candidates set contains at most 5 palindromes, each palindrome takes up O(log(n)) space.

The full solution can be found near the top of the page.