Find the Closest Palindrome

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.

Example 1:

Input: n = "123" Output: "121"

Example 2:

Input: n = "1" Output: "0" Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.

Constraints:

• 1 <= n.length <= 18
• n consists of only digits.
• n does not have leading zeros.
• n is representing an integer in the range [1, 10^18 - 1].

def nearest_palindrome(n):
    """
    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.

    For example:
    nearest_palindrome("123") == "121"
    nearest_palindrome("1") == "0"
    nearest_palindrome("12345") == "12321"
    nearest_palindrome("12321") == "12221"
    """
    num = int(n)
    length = len(n)
    prefix = n[:(length + 1) // 2]

    candidates = []

    # Candidate 1: prefix + reversed(prefix)
    palindrome1 = prefix + prefix[:length // 2][::-1]
    candidates.append(int(palindrome1))

    # Candidate 2: (prefix - 1) + reversed(prefix - 1)
    prefix_minus_1 = str(int(prefix) - 1)
    palindrome2 = prefix_minus_1 + prefix_minus_1[:len(prefix_minus_1) - (length % 2)][::-1] if prefix_minus_1 != '-1' else '0' * (length - 1 or 1)
    candidates.append(int(palindrome2))

    # Candidate 3: (prefix + 1) + reversed(prefix + 1)
    prefix_plus_1 = str(int(prefix) + 1)
    palindrome3 = prefix_plus_1 + prefix_plus_1[:len(prefix_plus_1) - (length % 2)][::-1]
    
    if len(prefix_plus_1) > len(prefix):
        palindrome3 = '1' + '0' * (length - 1)
    candidates.append(int(palindrome3))

    closest = -1
    min_diff = float('inf')

    for candidate in candidates:
        if candidate == num:
            continue

        diff = abs(candidate - num)

        if diff < min_diff:
            min_diff = diff
            closest = candidate
        elif diff == min_diff:
            closest = min(closest, candidate)

    return str(closest)


# Naive solution
# def is_palindrome(n):
#   s = str(n)
#   return s == s[::-1]

# def nearest_palindrome_naive(n):
#   num = int(n)
#   i = 1
#   while True:
#     if is_palindrome(num - i) and num - i >= 0:
#       return str(num - i)
#     if is_palindrome(num + i):
#       return str(num + i)
#     i += 1


# Example usage
print(nearest_palindrome("123"))
print(nearest_palindrome("1"))
print(nearest_palindrome("12345"))
print(nearest_palindrome("12321"))
print(nearest_palindrome("99"))
print(nearest_palindrome("100"))
print(nearest_palindrome("10"))

Explanation:

The optimal solution generates three candidate palindromes: one formed by mirroring the first half of the input number, one formed by mirroring the first half after decrementing it, and one formed by mirroring the first half after incrementing it. It then iterates through these candidates, calculates the absolute difference between each candidate and the original number, and returns the candidate with the smallest difference. If there is a tie, it returns the smaller of the tied candidates.

Big O Runtime Analysis:

The runtime complexity is dominated by the string manipulations and integer comparisons. Generating the candidates involves slicing and reversing strings, which takes O(length) time, where length is the number of digits in the input. The loop iterates a fixed number of times (at most 3). Therefore, the overall time complexity is O(length).

Big O Space Usage Analysis:

The space complexity is O(length) because we store the candidates as strings, which can have a length equal to the number of digits in the input. We also store a few integer variables, which take constant space.

Edge Cases:

1. Input is a single digit: If the input is a single digit, the closest palindrome is 0 if the input is not 0, or 1 if the input is 0.
2. Input is a palindrome: If the input is already a palindrome, the algorithm correctly finds the next closest palindrome (smaller or larger). An example: if the input is "12321", the algorithm should return "12221".
3. Input consists of all 9s: If the input consists of all 9s, the closest palindrome is a number with 1 followed by all 0s, one more digit than the input. For example, if the input is "99", the output should be "101".
4. Decrementing the prefix results in a negative number: if decrementing the prefix of the first half of the number results in a negative number, we create "0" * (length -1 or 1)
5. Incrementing the prefix increases the length: if incrementing the prefix of the first half of the number increases the length, we create '1' + '0' * (length -1)