30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 680. Valid Palindrome II

Determine whether a string can become a palindrome by deleting at most one character: use a two-pointer scan from both ends and allow a single mismatch where you skip either the left or right character.

Asked at:

DESCRIPTION

Input:


s = "racecar"

Output:


true

Explanation: The string is already a palindrome, so no deletion is needed. Return true.

Constraints:

1 <= s.length <= 10^5
s consists of lowercase English letters only
You can delete at most one character

Understanding the Problem

Let's understand what we're being asked to do. We have a string like 'racecar' and need to determine if we can make it a palindrome by deleting at most one character.

Tracing through 'racecar': it's already a palindrome (reads the same forwards and backwards), so we return true without deleting anything.

Now consider 'raceacar': it's NOT a palindrome as-is. But if we delete the 'a' at index 4, we get 'racecar' which IS a palindrome! So we return true.

Important constraint: We can delete at most one character, not multiple characters. If a string needs more than one deletion to become a palindrome, return false.

Edge cases to consider: What if the string is already a palindrome? (return true, no deletion needed). What if it's empty or has one character? (always true). What if removing either the left OR right mismatched character could work?

Brute Force Approach

The brute force approach tries deleting each character one at a time and checks if the resulting string is a palindrome. For each position i from 0 to n-1, create a new string without character at index i, then scan that string to verify if it's a palindrome. If any deletion produces a palindrome, return true; otherwise return false. This approach is simple but inefficient because it performs many redundant palindrome checks.

def can_become_palindrome(s):
    """
    Brute force: Try deleting each character one at a time.
    For each deletion, check if the resulting string is a palindrome.
    """
    n = len(s)
    
    # Helper function to check if a string is a palindrome
    def is_palindrome(string):
        left = 0
        right = len(string) - 1
        
        while left < right:
            if string[left] != string[right]:
                return False
            left += 1
            right -= 1
        
        return True
    
    # Try deleting each character at position i
    for i in range(n):
        # Create new string without character at index i
        new_string = s[:i] + s[i+1:]
        
        # Check if this new string is a palindrome
        if is_palindrome(new_string):
            return True
    
    # If no deletion produces a palindrome, return False
    return False

Start: Check if string can become palindrome by deleting at most one character

0 / 17

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) We try n possible deletions, and each palindrome check takes O(n) time, resulting in O(n²) total time

Space Complexity: O(n) Creating a new string for each deletion attempt requires O(n) space

Building Intuition

When checking if a string is a palindrome, we compare characters from both ends moving inward. For 'racecar', we compare 'r' with 'r' (match), then 'a' with 'a' (match), continuing until we meet in the middle.

When we find a mismatch, we have exactly two choices: skip the left character OR skip the right character. One of these must form a palindrome for the answer to be true.

By scanning from both ends simultaneously, we can detect the first mismatch immediately. At that point, we only need to check two possibilities (skip left or skip right) rather than trying all possible deletions.

This transforms a potentially expensive operation (checking all n possible deletions) into a simple two-pointer scan with at most two additional checks.

Imagine two people walking toward each other from opposite ends of a hallway, checking if floor tiles match.

If they find tiles that don't match, one person says 'maybe skip MY tile' and the other says 'maybe skip MY tile'. They each try their suggestion and see if the remaining tiles all match.

This is exactly how we handle the mismatch: when left and right characters don't match, we try skipping the left character (check if s[left+1...right] is a palindrome) OR skipping the right character (check if s[left...right-1] is a palindrome).

Common Mistakes

Trying to delete multiple characters instead of stopping after the first mismatch - the problem allows at most ONE deletion

Only checking one skip option (left OR right) instead of both - when characters mismatch, BOTH possibilities must be tested

Not handling the case where the string is already a palindrome - this should return true immediately without any deletion

Incorrectly implementing the palindrome check for substrings after skipping - make sure to check the correct range [left+1, right] or [left, right-1]

Forgetting edge cases like single-character strings (always valid) or two-character strings (always valid with one deletion allowed)

Optimal Solution

The optimal approach uses a two-pointer technique scanning from both ends of the string. Start with pointers at the beginning and end, moving inward while characters match. When we encounter the first mismatch at positions left and right, we have exactly two options: skip the left character or skip the right character. Check if either s[left+1...right] or s[left...right-1] forms a palindrome. If either does, return true; otherwise return false. This eliminates redundant checks by only examining the two relevant substrings.

def valid_palindrome_with_deletion(s):
    """
    Check if string can become palindrome by deleting at most one character.
    Uses two-pointer technique with single mismatch handling.
    """
    def is_palindrome_range(left, right):
        """Helper to check if substring s[left:right+1] is palindrome."""
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True
    
    # Two pointers from both ends
    left = 0
    right = len(s) - 1
    
    # Scan inward while characters match
    while left < right:
        if s[left] != s[right]:
            # First mismatch: try skipping left OR right character
            skip_left = is_palindrome_range(left + 1, right)
            skip_right = is_palindrome_range(left, right - 1)
            return skip_left or skip_right
        
        left += 1
        right -= 1
    
    # No mismatches found - already a palindrome
    return True

Start: Check if string can become palindrome by deleting at most one character

0 / 14

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We scan the string once with two pointers in O(n) time, and in the worst case check two substrings for palindrome property, which is also O(n), giving us linear time overall

Space Complexity: O(1) We only use two pointer variables regardless of string length, requiring constant extra space

What We've Learned

Two-pointer palindrome validation: When checking palindromes, use pointers from both ends moving inward - this gives O(n) time and immediately identifies the first mismatch position, which is critical for problems allowing limited modifications.
Recursive mismatch handling: When you encounter a mismatch in a palindrome check, test both possibilities (skip left OR skip right character) by calling a helper function - don't assume which deletion will work, as either could form a valid palindrome.
Single-chance constraint pattern: For problems allowing "at most one" modification, use a boolean flag or count variable to track whether you've used your allowance - once a mismatch is handled, subsequent checks must be strict palindrome validation.
Helper function extraction: Separate the strict palindrome check into its own function that you can reuse - this prevents code duplication when testing the two skip scenarios and makes the logic clearer and less error-prone.
Early termination optimization: After finding the first mismatch, you only need to validate the remaining substring(s) as palindromes - no need to restart from the beginning, saving unnecessary comparisons and keeping time complexity at O(n).
Greedy validation pitfall: A common mistake is greedily choosing which character to skip based on local information - you must test BOTH skip options because the correct choice depends on the entire remaining substring structure, not just adjacent characters.

Test Your Understanding

Why is array the right data structure for this problem?

array provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid November, 2025

Microsoft

Mid-level

Mid November, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 680. Valid Palindrome II

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact