LeetCode 564: Find the Closest Palindrome Solution in Python – A Step-by-Step Guide

Imagine you’re given a number—like "1234"—and your task is to find the nearest number that reads the same forwards and backwards, such as "1221" or "1331," picking the one closest to 1234, almost like tuning a number to its palindromic twin. That’s the intriguing challenge of LeetCode 564: Find the Closest Palindrome, a hard-level problem that’s a fantastic way to practice string and number manipulation in Python. We’ll explore two solutions: the Best Solution, a greedy palindrome construction that’s efficient and clever, and an Alternative Solution, a brute-force search that’s thorough but impractical for large numbers. With detailed examples, clear code, and a friendly tone—especially for the greedy approach—this guide will help you find that palindrome, whether you’re new to coding or leveling up. Let’s mirror those digits and start searching!

What Is LeetCode 564: Find the Closest Palindrome?

In LeetCode 564: Find the Closest Palindrome, you’re given a string n representing a positive integer, and your task is to return the closest palindromic number as a string, where a palindrome reads the same forwards and backwards (e.g., "12321"). If there’s a tie, return the smaller palindrome. For example, with n = "123", the closest palindromes are "121" and "131", both 2 away, so return "121" (smaller). This problem builds on LeetCode 9: Palindrome Number for palindrome checking but requires constructing and comparing nearby palindromes.

Problem Statement

Input: n (str)—string representation of a positive integer.
Output: String—closest palindromic number (smallest if tied).
Rules: Palindrome must differ from n; closeness measured by absolute difference; handle edge cases like "1" or "999".

Constraints

1 <= n.length <= 18
n consists of digits, no leading zeros unless "0" itself.

Examples

Input: n = "123"

Output: "121"
Palindromes: "121" (diff = 2), "131" (diff = 8); "121" is closer and smaller.

Input: n = "1"

Output: "2"
Palindromes: "0" (diff = 1), "2" (diff = 1); "2" is larger but valid as "0" < 1.

Input: n = "10"

Output: "11"
Palindromes: "9" (diff = 1), "11" (diff = 1); "11" is closer to target.

Understanding the Problem: Finding the Closest Palindrome

To solve LeetCode 564: Find the Closest Palindrome in Python, we need to find the palindromic number closest to a given integer n, returning it as a string, with ties resolved by choosing the smaller palindrome. With lengths up to 18 digits, a brute-force search (checking all numbers) is impractical due to the vast range (10¹⁸). Instead, we can construct candidate palindromes by mirroring the left half of n and adjusting (e.g., incrementing or decrementing the middle), then compare distances. We’ll explore:

Best Solution (Greedy Palindrome Construction): O(d) time, O(d) space (d = digits)—fast and optimal.
Alternative Solution (Brute-Force Search): O(10^d) time, O(1) space—simple but slow.

Let’s dive into the greedy solution with a friendly breakdown!

Best Solution: Greedy Palindrome Construction

Why Greedy Wins

The greedy palindrome construction is the best for LeetCode 564 because it efficiently finds the closest palindrome in O(d) time and O(d) space (d = number of digits) by constructing three key candidates—mirroring the left half, incrementing it, and decrementing it—then selecting the closest one, avoiding exhaustive searches. It’s like crafting a palindrome mirror and tweaking it just enough to get as close as possible to the original number!

How It Works

Think of this as a palindrome-crafting wizard:

Step 1: Extract Left Half:

Take first half of n (e.g., "1234" → "12").

Step 2: Generate Candidates:

Mirror: Mirror left half (e.g., "1221").
Increment: Add 1 to left half, mirror (e.g., "1331").
Decrement: Subtract 1 from left half, mirror (e.g., "1111").

Step 3: Handle Edge Cases:

For "999", increment to "1001".
For "10", consider "9" and "11".

Step 4: Compare Distances:

Compute absolute differences from n.
Pick smallest, resolve ties by choosing smaller palindrome.

Step 5: Return Result:

Closest palindrome as string.

Why It Works:

Closest palindrome is near n’s mirrored form or one step away.
Three candidates cover all nearest options.

It’s like a palindrome-tuning artist!

Step-by-Step Example

Example: n = "1234"

Step 1: Left half = "12", length = 4.
Step 2: Candidates:

Mirror: "1221".
Increment: "13" → "1331".
Decrement: "11" → "1111".

Step 3: Distances:

|1234 - 1221| = 13.
|1234 - 1331| = 97.
|1234 - 1111| = 123.

Step 4: Min distance = 13, result = "1221".
Result: "1221".

Example: n = "999"

Step 1: Left half = "99", length = 3.
Step 2: Candidates:

Mirror: "999".
Increment: "100" → "1001".
Decrement: "98" → "989".

Step 3: Distances:

|999 - 999| = 0 (invalid, same as n).
|999 - 1001| = 2.
|999 - 989| = 10.

Step 4: Min distance = 2, result = "1001".
Result: "1001".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        # Step 1: Convert to integer and get length
        num = int(n)
        length = len(n)

        # Step 2: Handle small cases
        if num <= 10:
            return str(num - 1) if num > 1 else "1"
        if num == 11:
            return "9"

        # Step 3: Extract left half
        half_len = (length + 1) // 2
        left_half = int(n[:half_len])

        # Step 4: Generate candidate palindromes
        candidates = set()
        # Mirror left half
        mirror = str(left_half)
        palindrome = mirror + mirror[-2 if length % 2 else -1::-1]
        candidates.add(palindrome)

        # Increment left half
        incr_half = str(left_half + 1)
        incr_palindrome = incr_half + incr_half[-2 if length % 2 else -1::-1]
        candidates.add(incr_palindrome)

        # Decrement left half
        decr_half = str(left_half - 1)
        decr_palindrome = decr_half + decr_half[-2 if length % 2 else -1::-1]
        candidates.add(decr_palindrome)

        # Step 5: Handle edge cases (e.g., "999" or "1000")
        if num == 10 ** (length - 1):
            candidates.add(str(num - 1))
        if num == 10 ** length - 1:
            candidates.add(str(num + 1))

        # Step 6: Find closest palindrome
        candidates.discard(n)  # Exclude original number
        min_diff = float('inf')
        result = None
        for cand in candidates:
            cand_num = int(cand)
            diff = abs(cand_num - num)
            if diff < min_diff or (diff == min_diff and cand_num < int(result)):
                min_diff = diff
                result = cand

        return result

Lines 4-5: Convert n to int, get length.
Lines 8-10: Handle small numbers (1-11).
Lines 13-14: Extract left half.
Lines 17-27: Generate mirror, increment, decrement palindromes.
Lines 30-32: Add edge cases (e.g., "9", "1001").
Lines 35-43: Find closest by min difference, resolve ties.
Time Complexity: O(d)—string operations on digits.
Space Complexity: O(d)—candidate storage.

It’s like a palindrome-crafting genius!

Alternative Solution: Brute-Force Search

Why an Alternative Approach?

The brute-force search checks numbers incrementally above and below n, testing for palindromes, running in O(10^d) time and O(1) space (d = digits). It’s simple but impractical for large numbers, making it a good baseline for small inputs.

How It Works

Picture this as a palindrome-hunting explorer:

Step 1: Start from n.
Step 2: Check numbers up and down until palindrome found.
Step 3: Compare distances, pick closest.
Step 4: Return result.

It’s like a palindrome-seeker!

Step-by-Step Example

Example: n = "123"

Step 1: Check down: 122 → "221" (palindrome, diff = 2).
Step 2: Check up: 124 → 131 (palindrome, diff = 8).
Step 3: Min diff = 2, result = "221" → "121" (adjust logic).
Result: "121".

Code for Brute-Force Approach

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        def is_palindrome(s):
            return s == s[::-1]

        num = int(n)
        lower = num - 1
        upper = num + 1

        while True:
            lower_str = str(lower)
            upper_str = str(upper)
            if is_palindrome(lower_str) and lower_str != n:
                return lower_str
            if is_palindrome(upper_str) and upper_str != n:
                return upper_str
            lower -= 1
            upper += 1

Lines 5-18: Check numbers below and above n, return first palindrome.
Time Complexity: O(10^d)—exponential search range.
Space Complexity: O(1)—minimal extra space.

It’s a brute-force palindrome finder!

Comparing the Two Solutions

Greedy (Best):

Pros: O(d), O(d), fast.
Cons: Logic-based.

Brute-Force (Alternative):

Pros: O(10^d), O(1), simple.
Cons: Impractical for large d.

Greedy wins for efficiency!

Additional Examples and Edge Cases

"9999": "10001".
"1000": "999".
"12321": "12421".

Greedy handles them all!

Complexity Recap

Greedy: Time O(d), Space O(d).
Brute-Force: Time O(10^d), Space O(1).

Greedy’s the speed champ!

Key Takeaways

Greedy: Palindrome crafting—learn at Python Basics!
Brute-Force: Number hunting.
Numbers: Palindromes are fun.
Python: Greedy or brute, your pick!

Final Thoughts: Find That Palindrome!

LeetCode 564: Find the Closest Palindrome in Python is a clever number challenge. Greedy palindrome construction is your fast track, while brute-force offers a thorough dive. Want more? Try LeetCode 9: Palindrome Number or LeetCode 680: Valid Palindrome II. Ready to mirror? Head to Solve LeetCode 564 on LeetCode and find that palindrome today!