Valid Palindrome II
An easy Two Pointers interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Two Pointers
- Sheets
- 1
- Core for
- 10 roles
The problem
Given a string, determine if it can become a valid palindrome by deleting at most one character.
Example 1
- Input
- s = "aba"
- Output
- true
- Why
- Already a palindrome.
Example 2
- Input
- s = "abca"
- Output
- true
- Why
- Deleting the character 'c' gives 'aba', which is a palindrome.
Example 3
- Input
- s = "abc"
- Output
- false
- Why
- No single deletion can make this a palindrome.
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters
How to think about it
Updated 2026-09-29Matching from the ends is completely deterministic until the first mismatch. At that single conflict, one of the two characters must be discarded. Testing both remaining subsegments with a standard palindrome check resolves the fate of the whole string without ever exploring further branches.
Approaches, worst first
Try all deletions
time O(n^2) · space O(n)
Generate every string obtained by removing character i, then test each one with a two-pointer palindrome check. Correct on small strings, but creating and scanning n strings of length n wastes quadratic work on prefixes that already matched.
Branch on first clashWrite this one
time O(n) · space O(1)
Pinch inwards with left and right pointers. On the first unequal pair, the answer is true if and only if s[left+1..right] or s[left..right-1] is a pure palindrome. Each subcheck runs in one linear scan with no further branching.
Where people lose marks · 3
- Greedily picking only one branch when characters match across both sides. In `cupuufpuuc`, discarding the left or right character creates different subproblems; skipping the OR check misses valid solutions.
- Allocating new substrings for the two inner checks. With s up to 10^5 characters, slicing creates large heap buffers when index-based pointer scans require zero extra memory.
- Allowing more than one deletion. The inner palindrome checker must be strict; re-triggering the deletion logic inside the branch accepts invalid strings.
The theory behind it
Two Pointers — the ground this problem stands on. All Two Pointers problems
What Two Pointers is
Two pointers is a search coordinated by two fingers placed on different entries of an ordered row, stepping inward toward each other or advancing at different speeds. Instead of scanning with nested loops that re-examine identical pairs, each pointer moves unidirectionally based on comparisons. Because every movement permanently prunes bad candidate combinations, the search inspects the collection in a single joint pass.
When to reach for it
Reach for two pointers when problems require finding index pairs, reversing sequences, trapping rainwater, or filtering duplicates in sorted arrays. When an input is already sorted and an exhaustive search takes quadratic time, opposing pointers meeting in the center often solve it linearly. Fast and slow pointer variations also detect cycles or locate midpoint nodes across linked sequences.
How the pattern works
Initialize pointers at opposing edges for convergent searches, or start both at the beginning to move at different speeds. Under a convergent setup, calculate current pair metrics; if the sum falls short of your target, advance the lower pointer rightward to increase value, and if it exceeds your target, shift the upper pointer leftward to decrease value. Each pointer move throws away only pairs that were already known to be wrong, so the right answer is never missed.
More Two Pointers problems
Target Roles
Core requirement for 10 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .