Valid Palindrome II - Video Solutions

Problem Overview: You are given a string s. The task is to determine whether it can become a palindrome after deleting at most one character. A palindrome reads the same forward and backward, so the challenge is detecting whether a single mismatch can be fixed by skipping one character.

This problem heavily relies on the two pointers pattern and careful string comparison. Instead of generating all possible deletions, you scan from both ends and react only when a mismatch appears.

Approach 1: Two Pointer Technique (O(n) time, O(1) space)

Use two pointers: left at the start of the string and right at the end. Move both pointers inward while characters match. When a mismatch appears, you get exactly one chance to delete a character. At that moment, check two possibilities: skip the left character (left + 1) or skip the right character (right - 1). If either remaining substring forms a palindrome, the answer is true.

The key insight is that only the first mismatch matters. After removing one character, the rest of the substring must already be a valid palindrome. This avoids brute-force deletion and keeps the scan linear. The algorithm performs a single pass over the string with at most one additional palindrome check, resulting in O(n) time and O(1) space. This pattern appears often in string problems that involve symmetry checks.

Approach 2: Recursive Two Pointers Method (O(n) time, O(n) recursion stack)

This variation applies the same idea but expresses the "skip one character" decision through recursion. Start with two pointers at the ends of the string. If characters match, recursively check the inner substring. When a mismatch occurs and deletion is still allowed, branch into two recursive calls: skip the left character or skip the right character.

A boolean flag tracks whether the deletion has already been used. Once the flag is consumed, further mismatches immediately fail. Although the total number of comparisons remains linear, recursive calls introduce stack usage up to O(n) space. This approach is easier to reason about conceptually because the recursive structure mirrors the palindrome definition.

Both approaches use the same core idea: a single mismatch can be corrected by removing one character. This greedy decision works because any valid solution must remove one of the two mismatching characters.

Recommended for interviews: The iterative two-pointer solution is the expected answer. It demonstrates mastery of the two pointers technique and achieves optimal O(n) time with constant space. Explaining the recursive variant can still help show deeper understanding of the decision process and the greedy nature of the first mismatch handling.