DSA AnimatorDSA animations
Valid Palindrome II LC #680 Easy Greedy Two Pointers
Problem

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

Example 1
Input: s = "abca"
Output: true
Explanation: Delete 'c' to get "aba".
Example 2
Input: s = "abc"
Output: false
Explanation: Neither skip-l nor skip-r yields a palindrome.
Constraints: 1 ≤ s.length ≤ 10⁵ | s consists of lowercase English letters
Try Examples
Custom:
Approach
Greedy two pointers — on mismatch, try skip-l OR skip-r
Scan inward while chars match. At first mismatch, use your one deletion: check if s[l+1..r] or s[l..r-1] is a palindrome via isPalin. Either works → true. O(n) time, O(1) space.
String Strip
deleted char
remaining substring
— No deletion yet — scan with l and r
Variables
l
0
r
—
skip
—
branch
—
result
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Init l = 0, r = n−1
2
While l < r: if s[l] == s[r], move both inward
3
On mismatch: try isPalin(s, l+1, r) OR isPalin(s, l, r−1)
4
Either substring is palindrome → return true
5
Neither works → false; loop ends with no mismatch → true
Time
O(n)
Space
O(1)
Why This Works

Greedy: only act at the first mismatch. Before that point, chars already matched — no deletion needed there. With exactly one deletion allowed, only two choices exist: drop the left char or the right char. Run isPalin on each remaining substring; if either is a palindrome, the answer is true. Both must fail for false.

How to solve Valid Palindrome II

LeetCode 680 · Medium · Strings · Pattern: Two Pointers

Why the obvious approach is slow

Trying to delete every character, then checking, is O(n²). Only the first mismatch matters.

The key idea

Compare characters from both ends with two pointers. At the first mismatch, you have exactly two options: skip the left character, or skip the right one. If either remaining part is a palindrome, the answer is true.

Remember

One deletion allowed means two choices at the first mismatch. Check both, each in linear time.

Run the animation above on your own input, or watch the 1:07 video explanation of Valid Palindrome II with a dry run and Java code.

More Strings problems