← DSA Atlas
Dedicated problem page · #680

Valid Palindrome II

EasyTwo PointersConverging pointers with one allowed skipTwo pointers
Solve on LeetCode ↗
680
EasyTwo PointersTwo pointersConverging pointers with one allowed skip

Valid Palindrome II

Given a string s, return true if s can be made a palindrome by deleting at most one character (deleting zero characters is allowed, so an already-palindromic string qualifies).

Open official problem prompt ↗
In plain English

Decide whether the string is at most one deletion away from reading the same forwards and backwards.

Picture it like this

Reading a word aloud from both ends toward the middle; if one letter is out of place you get a single 'mulligan' to cover it, then everything else must line up.

Example
Input
s = "abca"
Output
true
Why
Deleting 'c' leaves "aba", which is a palindrome.
Constraints
1 <= s.length <= 10^5s consists of lowercase English letters
Pattern lesson

See the pattern, then code

Converging pointers with one allowed skip
Recognition clue

You are checking a palindrome from both ends, but with a small allowance for imperfection ('at most one deletion'). That budget-of-one on a symmetric scan is the two-pointer skip signal.

↗
Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. Walk inward from both ends while characters match. The first mismatch is the only place a deletion could help, so try skipping the left character or the right character and verify the remainder is a clean palindrome.

New words, made simpleKnow these before the algorithm
Palindrome
A sequence that reads identically left-to-right and right-to-left.
Converging pointers
Two indices that start at opposite ends and move toward each other.
Skip
Ignoring one character to simulate its deletion.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Try every deletion

Rebuilding and re-checking n strings is quadratic and needless when only one spot can ever matter.

For each index, remove it and test whether the rest is a palindrome.

Time O(n^2)Space O(n)
Best choiceTwo pointers with a single branch

A single inward pass plus at most one linear verification of a subrange.

Scan inward until a mismatch, then check the two ways to spend the one allowed deletion.

Time O(n)Space O(1)
The rule we keep true

Invariant

Every character pair strictly outside the current [left, right] window has already been confirmed equal, so only the untested inner window can decide the answer.

Why this is correct

Reasoning

If the string needs a deletion, the earliest mismatch pins down the culprit: either s[left] or s[right] must be the character removed, because all pairs before it already matched. Checking both candidate ranges covers every valid single-deletion outcome; if neither is a palindrome, no single deletion can fix it.

The algorithm in three movesSay these aloud before coding
1Move left and right pointers inward while s[left] == s[right]

left=1 ('b'), right=2 ('c') -> mismatch

2On the first mismatch, form two candidate substrings: skip the left char or skip the right char

try skip-left: is_palindrome(2,2) on 'c'? yes -> short-circuits to true

3Return true if either candidate range is a palindrome

(skip-right: is_palindrome(1,1) on 'b' would also be yes)

4If the pointers cross with no mismatch, it was already a palindrome

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
a0
b1
c2
a3
1 · Reads[0]='a', s[3]='a'
2 · AskDo the ends match?
3 · Update stateleft=0, right=3
4 · ResultMatch; move inward to left=1, right=2.
Key takeaway

The outer 'a's match; the mismatch at 'b' vs 'c' triggers one skip attempt that succeeds.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-10Helper is_palindrome(i, j)

    A plain two-pointer palindrome check over a subrange, reused for both deletion candidates.

  2. 2
    Lines 11-17Main inward scan

    Advance while characters match; the first mismatch is the single decision point.

  3. 3
    Lines 15Branch on the one allowed skip

    Skipping left (i+1, j) or right (i, j-1) captures both possible deletions; either passing suffices.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Already a palindrome (e.g. "aba") — the loop finishes with no mismatch and returns true using zero deletions
  • Single character or empty-after-constraint minimum length string — vacuously a palindrome
  • Mismatch at the very center where either skip leaves a length-0 or length-1 range
!

Common beginner mistakes

  • Allowing more than one deletion by recursing repeatedly instead of checking exactly the two branches at the first mismatch
  • Forgetting that deleting zero characters is permitted, so a clean palindrome must return true
  • Rebuilding sliced strings (s[i+1:j+1]) inside the check, turning O(1) extra space into O(n) and slowing large inputs
Check your understanding

Why is it enough to test only skipping s[left] or s[right] at the first mismatch, rather than considering deletions elsewhere?

More in Two Pointers

#153SumSorted two-pointer scan around a fixed anchor#11Container With Most WaterConverging pointers on a width-vs-height tradeoff#184SumTwo fixed anchors plus a sorted two-pointer inner scan#26Remove Duplicates from Sorted ArraySlow/fast in-place overwrite#31Next PermutationFind pivot, swap successor, reverse suffix#42Trapping Rain WaterConverging pointers tracking left/right maxima