Leetcode 564. Find the Closest Palindrome

Let's understand what we're being asked to do. We have a numeric string n like '123' and need to find the closest palindrome that is different from n.

For example, if n = '123', some palindromes near it are '121' (distance 2), '131' (distance 8), '111' (distance 12). The closest is '121'.

Important constraint: The palindrome must be different from n itself. So if n = '121' (already a palindrome), we can't return '121' - we need the next closest like '111' or '131'.

Key insight: We need to consider multiple candidate palindromes: mirroring the prefix, incrementing/decrementing the middle, and boundary cases like 999...999 or 100...001.

Edge cases to consider: What if n = '1'? (return '0'). What if n = '99'? (return '101', crossing a power-of-10 boundary). What if there's a tie in distance? (return the smaller palindrome).

A palindrome is determined entirely by its first half - the second half is just a mirror. For n = '12345', if we take the first half '123' and mirror it, we get '12321'.

But this mirrored palindrome might not be the closest! We also need to consider what happens if we increment or decrement the middle part before mirroring.

By adjusting the prefix (the part that determines the palindrome) up or down by 1, we generate nearby palindrome candidates. For n = '12345', candidates include: mirroring '123' → '12321', mirroring '124' → '12421', mirroring '122' → '12221'.

We also need boundary cases: numbers like '999' (next palindrome is '1001') or '1000' (previous palindrome is '999'). These cross power-of-10 boundaries.

Think of a palindrome as a folded piece of paper - what you write on one side appears on the other. The challenge is finding which 'fold point' (prefix) gives us the closest result.

Imagine n = '1234'. We can try folding at different points: '12|34' → mirror to get '1221', or adjust the left side first: '13|34' → '1331', or '11|34' → '1111'. We generate all reasonable candidates and pick the closest.

Don't forget edge cases: '9999' can't just increment the middle - it needs to become '10001' (one digit longer!).

Generate candidate palindromes by: (1) mirroring the prefix of n, (2) incrementing the prefix and mirroring, (3) decrementing the prefix and mirroring, and (4) including boundary cases like 10^k - 1 (all 9s) and 10^k + 1 (100...001). For each candidate, compute the absolute difference from n. Select the candidate with the smallest difference, breaking ties by choosing the smaller value. This approach systematically covers all nearby palindromes without exhaustive search.

def nearest_palindrome(n):
    """
    Find the closest palindrome to n (different from n).
    Ties broken by smaller value.
    """
    length = len(n)
    num = int(n)
    candidates = []
    
    # Boundary cases: 999...999 (length-1) and 100...001 (length+1)
    candidates.append(10**length + 1)  # 100...001
    candidates.append(10**(length - 1) - 1)  # 999...999
    
    # Get prefix (first half, including middle for odd length)
    prefix_len = (length + 1) // 2
    prefix = int(n[:prefix_len])
    
    # Generate candidates by mirroring prefix-1, prefix, prefix+1
    for delta in [-1, 0, 1]:
        new_prefix = str(prefix + delta)
        
        # Mirror the prefix to create palindrome
        if length % 2 == 0:
            # Even length: mirror entire prefix
            candidate = new_prefix + new_prefix[::-1]
        else:
            # Odd length: mirror all but middle character
            candidate = new_prefix + new_prefix[-2::-1]
        
        candidates.append(int(candidate))
    
    # Find closest palindrome different from n
    best = -1
    min_diff = float('inf')
    
    for cand in candidates:
        # Skip if same as n
        if cand == num:
            continue
        
        diff = abs(cand - num)
        
        # Update if closer, or same distance but smaller
        if diff < min_diff or (diff == min_diff and cand < best):
            min_diff = diff
            best = cand
    
    return str(best)

• Candidate generation strategy: For palindrome problems with numeric constraints, generate a small set of strategic candidates rather than checking all possibilities - mirror the prefix to create base palindromes, then add boundary cases (999...999 and 100...001) which are often closest to numbers near powers of 10.
• Prefix mirroring technique: To generate palindrome candidates, take the first half (including middle for odd length) of the number, try incrementing/decrementing it by 1, then mirror it to the second half - this creates the three most likely candidates while maintaining palindrome structure efficiently.
• Edge case enumeration: Always include 10^k - 1 (all 9s) and 10^k + 1 (100...001) as candidates because numbers near power-of-10 boundaries often have their closest palindrome at these special values (e.g., 1000 → 999, 99 → 101), which aren't generated by simple mirroring.
• String-based arithmetic for large numbers: When dealing with numbers up to 18 digits that exceed standard integer limits, use string manipulation for comparisons and adjustments rather than converting to long/int - this prevents overflow and maintains precision throughout the algorithm.
• Tie-breaking with comparison logic: When two candidates have equal distance, implement explicit smaller-value selection by comparing absolute differences first, then choosing the numerically smaller candidate - don't rely on iteration order as it may not guarantee correct tie-breaking.
• Self-exclusion validation: Always filter out the original number from candidates before selecting the closest - a common bug is returning the input itself when it's already a palindrome, violating the "different from n" requirement.