LeetCode 680: Valid Palindrome II Solution in Python – A Step-by-Step Guide

What Is LeetCode 680: Valid Palindrome II?

In LeetCode 680: Valid Palindrome II, you’re given a string s, and your task is to determine if it can be made into a palindrome by removing at most one character. A palindrome is a string that reads the same forward and backward (e.g., "racecar"). Return True if such a removal is possible, False otherwise. For example, with s = "aba", it’s already a palindrome, so return True. With s = "abca", removing 'c' makes "aba", so return True. With s = "abc", no single removal works, so return False. This problem tests your ability to validate palindromes with a single modification efficiently.

Problem Statement

• Input:
• s: String of lowercase letters.
• Output: A boolean—True if palindrome possible with ≤ 1 removal, False otherwise.
• Rules:
• Remove at most one character.
• Check if resulting string is a palindrome.
• String contains only lowercase English letters.

Constraints

• 1 ≤ s.length ≤ 10⁵.

Examples

• Input: s = "aba"
• Output: True (Already palindrome, no removal needed)
• Input: s = "abca"
• Output: True (Remove 'c' → "aba")
• Input: s = "abc"
• Output: False (No single removal makes palindrome)
• Input: s = "deeee"
• Output: True (Remove one 'e' → "deee")

These examples set the string—let’s solve it!

Understanding the Problem: Validating with One Removal

To solve LeetCode 680: Valid Palindrome II in Python, we need to check if a string can become a palindrome by removing at most one character. A brute-force approach—trying to remove each character and checking—would be O(n²) (n removals, O(n) check each), inefficient for s.length ≤ 10⁵. Since we’re looking for palindrome validity with one skip, we can optimize using two pointers or iteration. We’ll use:

• Best Solution (Two-Pointer with Skip): O(n) time, O(1) space—fast and elegant.
• Alternative Solution (Brute-Force with Character Removal): O(n²) time, O(n) space—simple but slow.

Let’s start with the two-pointer solution, breaking it down for beginners.

Best Solution: Two-Pointer with Skip

Why This Is the Best Solution

The two-pointer with skip approach is the top choice for LeetCode 680 because it’s highly efficient—O(n) time with O(1) space—and uses a clever strategy: scan from both ends with two pointers, and when a mismatch occurs, try skipping one character from either side to see if the rest forms a palindrome. It fits constraints (s.length ≤ 10⁵) perfectly and is intuitive once you see the pointer logic. It’s like checking a mirror with one chance to fix a smudge!

How It Works

Think of this as a mirror checker:

• Step 1: Initialize Pointers:
• left = 0, right = len(s) - 1.
• Step 2: Scan with Skip Option:
• While left < right:
• If s[left] = s[right]: Move pointers inward.
• If mismatch:
• Try skipping left: Check if s[left+1:right+1] is palindrome.
• Try skipping right: Check if s[left:right] is palindrome.
• Return True if either works, False otherwise.
• Step 3: Helper Function:
• isPalindrome(s, start, end): Check substring validity.
• Step 4: Return Result:
• Return True if valid with ≤ 1 skip, False otherwise.

It’s like a skip balancer—check and adjust!

Step-by-Step Example

Example: s = "abca"

• Step 1: left = 0, right = 3.
• Step 2: Scan:
• left=0 ('a'), right=3 ('a'): Match, left=1, right=2.
• left=1 ('b'), right=2 ('c'): Mismatch.
• Skip left (1): Check s[2:3] = "c", not palindrome, but proceed.
• Skip right (2): Check s[1:2] = "b", not palindrome.
• Full check needed:
• Helper: s[2:4] = "ca", False.
• Helper: s[1:3] = "bc", False.
• But adjust logic: Skip left, check "aca" (remove 'b'), True.
• Step 3: Return True (one skip works).
• Output: True.

Example: s = "abc"

• Step 1: left = 0, right = 2.
• Step 2: Scan:
• left=0 ('a'), right=2 ('c'): Mismatch.
• Skip left: s[1:3] = "bc", False.
• Skip right: s[0:2] = "ab", False.
• Step 3: No single skip works, return False.
• Output: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def validPalindrome(self, s: str) -> bool:
        # Step 1: Helper function to check palindrome
        def isPalindrome(s: str, start: int, end: int) -> bool:
            while start < end:
                if s[start] != s[end]:
                    return False
                start += 1
                end -= 1
            return True

        # Step 2: Two-pointer scan with skip
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                # Try skipping one character
                return (isPalindrome(s, left + 1, right) or 
                        isPalindrome(s, left, right - 1))

        # Step 3: Return True if no skips needed
        return True

• Lines 4-11: isPalindrome: Check substring for palindrome property.
• Lines 14-23: Scan:
• Move pointers if match, try skipping left or right on mismatch.
• Line 26: Return: True if palindrome without skip or with one skip.
• Time Complexity: O(n)—single pass with two O(n) sub-checks.
• Space Complexity: O(1)—no extra space beyond recursion.

This is like a palindrome fixer—skip and verify!

Alternative Solution: Brute-Force with Character Removal

Why an Alternative Approach?

The brute-force with character removal approach tries removing each character—O(n²) time, O(n) space. It’s simpler conceptually, generating each possible string and checking, but inefficient for large n. It’s like testing every erasure until one works!

How It Works

Picture this as an erasure tester:

• Step 1: For each index i:
• Remove character at i.
• Step 2: Check if resulting string is palindrome:
• Use palindrome check function.
• Step 3: Return True if any removal works, False otherwise.

It’s like a string eraser—remove and test!

Step-by-Step Example

Example: s = "abca"

• Step 1: Try removals:
• i=0: "bca", not palindrome.
• i=1: "aca", palindrome, return True.
• Output: True.

Example: s = "abc"

• Step 1: Try removals:
• i=0: "bc", not palindrome.
• i=1: "ac", not palindrome.
• i=2: "ab", not palindrome.
• Step 2: No removal works, return False.
• Output: False.

Code for Brute-Force Approach

Copy codeclass Solution:
    def validPalindrome(self, s: str) -> bool:
        # Step 1: Helper function to check palindrome
        def isPalindrome(s: str) -> bool:
            return s == s[::-1]

        # Step 2: Try removing each character
        for i in range(len(s)):
            new_s = s[:i] + s[i+1:]
            if isPalindrome(new_s):
                return True

        # Step 3: Return True if original is palindrome
        return isPalindrome(s)

• Lines 4-6: isPalindrome: Check if string equals its reverse.
• Lines 9-13: Try removals:
• Remove each char, check if result is palindrome.
• Line 16: Return: True if original or one removal works.
• Time Complexity: O(n²)—n removals, O(n) check each.
• Space Complexity: O(n)—new string storage.

It’s a removal checker—erase and verify!

Comparing the Two Solutions

• Two-Pointer (Best):
• Pros: O(n) time, O(1) space, fast and minimal.
• Cons: Skip logic less obvious.
• Brute-Force (Alternative):
• Pros: O(n²) time, O(n) space, straightforward.
• Cons: Slower, more space.

Two-pointer wins for efficiency.

Additional Examples and Edge Cases

• Input: s = ""
• Output: True.
• Input: s = "a"
• Output: True.
• Input: s = "abcd"
• Output: False.

Two-pointer handles these well.

Complexity Breakdown

• Two-Pointer: Time O(n), Space O(1).
• Brute-Force: Time O(n²), Space O(n).

Two-pointer is optimal.

Key Takeaways

• Two-Pointer: Skip balancing—smart!
• Brute-Force: Removal testing—clear!
• Palindromes: Checking is fun.
• Python Tip: Pointers rock—see Python Basics.

Final Thoughts: Solve That Case

LeetCode 680: Valid Palindrome II in Python is a fun palindrome challenge. Two-pointer with skip offers speed and elegance, while brute-force provides a clear baseline. Want more? Try LeetCode 125: Valid Palindrome or LeetCode 5: Longest Palindromic Substring. Ready to detect? Head to Solve LeetCode 680 on LeetCode and validate that palindrome today!