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.
    """
    num = int(n)
    length = len(n)
    prefix = n[:(length + 1) // 2]

    candidates = []

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

    # Case 2: (prefix - 1) + reversed(prefix - 1) or (prefix - 1) + reversed(prefix - 1)[:-1]
    prefix_minus_one = str(int(prefix) - 1)
    palindrome2 = prefix_minus_one + prefix_minus_one[:len(prefix_minus_one) - (length + 1) // 2][::-1]
    candidates.append(int(palindrome2))

    # Case 3: (prefix + 1) + reversed(prefix + 1) or (prefix + 1) + reversed(prefix + 1)[:-1]
    prefix_plus_one = str(int(prefix) + 1)
    palindrome3 = prefix_plus_one + prefix_plus_one[:len(prefix_plus_one) - (length + 1) // 2][::-1]
    candidates.append(int(palindrome3))

    # Handle edge cases like single digit and all 9s
    if len(n) == 1:
        return str(num - 1 if num > 0 else 1)

    if all(c == '9' for c in n):
        return str(int('1' + '0' * len(n))) + '1'

    closest = float('inf')
    result = None

    for candidate in candidates:
        if candidate != num:
            diff = abs(candidate - num)
            if diff < closest:
                closest = diff
                result = candidate
            elif diff == closest:
                result = min(result, candidate)

    return str(result)

# Example Usage
print(nearest_palindrome("123")) # Output: 121
print(nearest_palindrome("1"))   # Output: 0
print(nearest_palindrome("12345")) # Output: 12321
print(nearest_palindrome("999")) # Output: 1001
print(nearest_palindrome("100")) # Output: 99

Explanation:

The function nearest_palindrome(n) finds the nearest palindrome to a given number n. It handles various edge cases and ensures the returned palindrome is the closest one.

1. Convert to Integer and Extract Prefix:

   • The input string n is converted to an integer num and its length is stored.
   • The prefix of n which is used to construct potential palindromes is extracted.

2. Generate Palindrome Candidates:

   • Case 1: Create a palindrome using the extracted prefix.
   • Case 2: Create a palindrome using prefix - 1.
   • Case 3: Create a palindrome using prefix + 1.

3. Handle Edge Cases:

   • If n is a single digit, return n - 1 (or 1 if n is 0).
   • If n consists of all 9s (e.g., "999"), return the next palindrome (e.g., "1001").

4. Find the Closest Palindrome:

   • Iterate through the candidate palindromes and find the one with the minimum absolute difference from num.
   • If there's a tie, pick the smaller palindrome.

5. Return the Result:

   • The closest palindrome found is returned as a string.

Edge Cases Handled:

• Single-digit numbers: For example, if n is "1", the function correctly returns "0".
• Numbers consisting of all 9s: For example, if n is "999", the function returns "1001".
• General Palindrome Generation: The code generates palindromes by reflecting the prefix, ensuring that it handles both even and odd length inputs correctly.
• Tie-breaking: If two palindromes are equally close, the smaller one is chosen.

Big O Runtime Analysis:

The runtime of the nearest_palindrome function is dominated by a few key operations:

1. String Slicing and Reversal: These operations take O(k) time, where k is the length of the prefix (which is approximately half the length of the input string n).
2. Integer Conversions and Arithmetic: Converting the string to an integer and performing arithmetic operations (+1, -1) also takes O(k) time, where k is the length of the prefix.
3. Iteration through Candidates: The function iterates through a fixed number of palindrome candidates (at most 3). This is O(1).
4. Finding the Closest Palindrome: The loop that iterates through the candidates has a complexity of O(1) because it has a fixed number of candidates.

Overall, the dominant operations are string slicing/reversal and integer conversions/arithmetic, which depend on the length of the input string. Therefore, the overall runtime complexity is O(n), where n is the length of the input string.

Big O Space Usage Analysis:

The space complexity of the nearest_palindrome function is determined by the space used to store the palindrome candidates and the intermediate strings.

1. Palindrome Candidates: The candidates list stores at most 3 palindrome integers. This takes O(1) space because it is a fixed number of candidates regardless of the input size.
2. Prefix and Palindrome Strings: The prefix string, as well as the palindrome strings generated from it, take O(k) space, where k is the length of the prefix. Since k is approximately half the length of the input string n, this is O(n/2) which simplifies to O(n).

Therefore, the overall space complexity is O(n), where n is the length of the input string.