Valid Palindrome II

Difficulty: Easy Source: NeetCode

Problem

Given a string s, return true if the string can be a palindrome after deleting at most one character from it.

Example 1: Input: s = "aba" Output: true

Example 2: Input: s = "abca" Output: true (delete 'c')

Example 3: Input: s = "abc" Output: false

Constraints:

• 1 <= s.length <= 10^5
• s consists only of lowercase English letters

Prerequisites

Before attempting this problem, you should be comfortable with:

• Valid Palindrome (LeetCode 125) — checking if a string is a palindrome with two pointers
• Two Pointers — moving inward from both ends and branching on a mismatch

1. Brute Force

Intuition

Try deleting every character one at a time and check if the resulting string is a palindrome. The first deletion that produces a palindrome means we return True. If no single deletion works, return False. Simple to understand but slow — we’re doing n palindrome checks each costing O(n).

Algorithm

1. Define a helper is_palindrome(t) that returns whether string t reads the same forward and backward.
2. If s is already a palindrome, return True.
3. For each index i from 0 to len(s) - 1:
   • Build t = s[:i] + s[i+1:] (delete character at i).
   • If is_palindrome(t), return True.
4. Return False.

Solution

def validPalindrome(s):
    def is_palindrome(t):
        return t == t[::-1]

    if is_palindrome(s):
        return True

    for i in range(len(s)):
        if is_palindrome(s[:i] + s[i + 1:]):
            return True

    return False


print(validPalindrome("aba"))   # True
print(validPalindrome("abca"))  # True
print(validPalindrome("abc"))   # False

Complexity

• Time: O(n²)
• Space: O(n)

2. Two Pointers with One Skip

Intuition

Walk inward from both ends with two pointers, exactly like a normal palindrome check. The moment we hit a mismatch at positions left and right, we know we must skip one of those two characters. We check both options: does s[left+1 .. right] form a palindrome, or does s[left .. right-1]? If either does, we can fix the string with one deletion. We only ever need to branch once — if neither half is a palindrome, no single deletion can save us.

Algorithm

1. Define a helper is_palindrome(t, l, r) that checks if t[l..r] is a palindrome using two pointers.
2. Initialize left = 0, right = len(s) - 1.
3. While left < right:
   • If s[left] == s[right]: move both pointers inward.
   • Else: return is_palindrome(s, left + 1, right) or is_palindrome(s, left, right - 1).
4. Return True (no mismatch found — already a palindrome).

Solution

def validPalindrome(s):
    def is_palindrome(t, l, r):
        while l < r:
            if t[l] != t[r]:
                return False
            l += 1
            r -= 1
        return True

    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return is_palindrome(s, left + 1, right) or is_palindrome(s, left, right - 1)
        left += 1
        right -= 1
    return True


print(validPalindrome("aba"))    # True
print(validPalindrome("abca"))   # True
print(validPalindrome("abc"))    # False
print(validPalindrome("deeee"))  # True

Complexity

• Time: O(n)
• Space: O(1)

Common Pitfalls

Skipping more than one character. The problem allows at most one deletion. Once you hit a mismatch, you must commit to one of the two choices and verify the remainder is a palindrome — you can’t keep skipping inside the helper.

Checking the wrong substrings on mismatch. When s[left] != s[right], the two candidate substrings are s[left+1 .. right] (skip left character) and s[left .. right-1] (skip right character). A common mistake is to check s[left+1 .. right-1], which skips both — that’s two deletions, not one.

Returning early on an already-valid palindrome. If the two-pointer walk completes without a mismatch, the string is already a palindrome, so return True without calling the helper.