Valid Palindrome II

On the first mismatch, branch: skip left or skip right

time O(n)space O(1)

A plain two-pointer palindrome check closes in from both ends and fails on the first mismatch. Allowing one deletion just means: at that exact mismatch, try both possible fixes — pretend the left character was the extra one (skip it) or pretend the right one was (skip it) — and check if either remaining substring is a clean palindrome. If either works, one deletion is enough.

Details

Animated on: s = "abca" — check whether it can become a palindrome by deleting at most one character.

Problem:Valid Palindrome IIEasy

On the first mismatch, branch: skip left or skip right

step 1 / 5

[0]

[1]

[2]

[3]

s="abca". Two pointers close in from both ends; on the first mismatch, try skipping either character.

l=0· arr[0] = a
r=3· arr[3] = a

Pseudocode

1FUNCTION validPalindrome(s):
2  l = 0, r = n - 1
3  WHILE l < r:
4    IF s[l] == s[r]: move l one step right, move r one step left
5    ELSE:
6      RETURN isPalin(s, l+1, r) or isPalin(s, l, r-1)
7  RETURN true  // (isPalin: two-pointer palindrome check on a range)
8  RETURN true

← / → step · space play · Home restart

Every step in words

Show all 5 steps

s="abca". Two pointers close in from both ends; on the first mismatch, try skipping either character.
s[0]='a' matches s[3]='a'. Move both pointers inward.
Mismatch: s[1]='b' != s[2]='c'. At most one deletion is allowed — try skipping s[1] OR skipping s[2] and see if what's left is a palindrome.
s[2..2] reads the same both ways — palindrome confirmed.
Skipping one character produces a palindrome — "abca" is valid with at most one removal.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Valid Palindrome II in the editor All Two Pointers problems Back to roadmap