Pattern visualizer
Valid Palindrome II
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. Animated on: s = "abca" — check whether it can become a palindrome by deleting at most one character..
On the first mismatch, branch: skip left or skip right
time O(n)space O(1)step 1 / 5
a
[0]b
[1]c
[2]a
[3]line 2
s="abca". Two pointers close in from both ends; on the first mismatch, try skipping either character.
Pseudocode
1FUNCTION validPalindrome(s):2 l = 0, r = n - 13 WHILE l < r:4 IF s[l] == s[r]: move l one step right, move r one step left5 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