Valid Palindrome II

Problem Description

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

Examples

Constraints

• 1 <= s.length <= 10⁵
• s consists of lowercase English letters.

Branching on the First Character Mismatch

We run standard two pointers checking from both ends. If the characters at left and right match, we simply shrink our pointers. If we encounter a mismatch s[left] != s[right], we have two options: we can either delete the character at left (and check if the remaining substring s[left+1 ... right] is a palindrome) or we can delete the character at right (and check if s[left ... right-1] is a palindrome). If either of these branches is a valid palindrome, the string is valid.

Solution 1: Double Pointer with Single Deletion Branching

Check characters from both ends and branch into a helper function upon finding a mismatch.

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                // Check both deletion options
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }

    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(l: int, r: int) -> bool:
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

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

#include <string>

class Solution {
private:
    bool isPalindrome(const std::string& s, int l, int r) {
        while (l < r) {
            if (s[l] != s[r]) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }

public:
    bool validPalindrome(std::string s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                // Check both deletion branches
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }
};

Complexity Analysis

• Time Complexity: O(n) because in the worst case we traverse the string at most twice (one partial check, and two parallel sub-checks).
• Space Complexity: O(1) auxiliary space as we only store pointers.

Where It Breaks

This algorithm only allows a single deletion. If the problem is generalized to allow up to k deletions, this simple branching approach becomes a backtracking or dynamic programming solution with O(n * k) complexity.

Common Mistakes

• Incorrect check ranges: Passing incorrect indices to the helper function, e.g. passing left + 1 and right - 1 together, which incorrectly simulates two deletions.
• Overlooking base cases: Returning false on the first mismatch instead of branching into the single-character deletion checks.

Frequently Asked Questions

Why does a simple greedy choice work? Once you find a mismatch, you can safely assume that any character outside the current bounds [left, right] has already been validated and matches its corresponding character on the other side.

Is recursion better for this? Recursion is unnecessary here because the branching logic only needs to run once. A simple iterative helper function avoids recursive frame stack allocations.

← All Problems