Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Walk two pointers inward checking for a palindrome. At the first mismatch you get exactly one delete — so greedily try both: skip the left char OR skip the right char, and return true if either remaining substring is a palindrome. O(n) time, O(1) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you realize the single delete forces the fix to be one of the two mismatched boundary characters — so you branch exactly once instead of exploring every deletion. Also whether you factor out a bounded palindrome helper cleanly.
Where candidates slip
Trying to be clever about *which* side to delete with a heuristic (e.g. always delete the side with the 'wrong' char) instead of just trying both, or restarting the whole scan after a delete and blowing up to O(n²) needlessly via substring copies.
How to stand out
Prove the greedy is complete: 'at a mismatch s[lo] != s[hi], a single delete can only remove s[lo] or s[hi] — deleting any interior char leaves the boundary mismatch unfixed. So checking both branches is exhaustive.'
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewlo at start, hi at ends[lo] == s[hi]?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Try Every Deletion
1Hint 1Explore hintHide hint
If you're allowed to delete one character, what's the most direct way to test the claim?
2Hint 2Explore hintHide hint
For each index i, build the string with s[i] removed, then check if that's a palindrome. Also check the original (zero deletes).
3Hint 3Explore hintHide hint
That's n+1 palindrome checks, each O(n), and each rebuilt string costs O(n) memory. Correct, but wasteful — most deletions are obviously pointless.
A · Core idea
The literal reading: 'delete at most one character' becomes 'try deleting each character (and also deleting none), and see if any result is a palindrome.'
Why it's the natural baseline. It mirrors the problem statement one-to-one — enumerate every allowed move and test the goal. No insight required, which is exactly why it's worth stating before optimizing.
Why it's wasteful. Almost every deletion is irrelevant. If s[lo] already equals s[hi] at the matching positions, deleting some character buried in the middle can't possibly help — yet brute force still rebuilds the whole string and rescans it. For n = 10⁵, O(n²) is ~10¹⁰ operations: a hard time-limit failure.
The key realization it leads to. When you watch brute force run, you notice the only deletions that ever matter are at the place where a plain palindrome check first breaks. That observation is what collapses n+1 candidate scans into a single forked check — the greedy approach below.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "abca"delete none
"abca" palindrome? b≠c
notrueC · Code with teaching comments
Reference implementation previewpublic boolean validPalindrome(String s) { if (isPalindrome(s)) return true; for (int i = 0; i < s.length(); i++) { String candidate = s.substring(0, i) + s.substring(i + 1); if (isPalindrome(candidate)) return true;Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Brute force exposes the waste: you rescan the entire string for deletions that can't affect a mismatch you haven't even reached yet. The fix only ever needs to happen at the first conflict — which is the seed of the greedy solution.
ComplexityO(n²) time, O(n) space — n+1 candidate strings × O(n) palindrome check = O(n²) time; each rebuilt string is O(n) space.
E · Edge cases and pitfalls3Forgetting the zero-delete case — an already-valid palindrome must return true.Explore edge casesHide edge cases
Pitfalls
- Forgetting the zero-delete case — an already-valid palindrome must return true.
- Rebuilding substrings inside the loop — O(n²) time and O(n) space, too slow for 10⁵.
- Assuming only one deletion 'side' matters without proof — here you brute everything, which hides the real insight.
Approach 2 of 2 · Optimal
Two Pointers + Greedy One-Delete Branch (Optimal)
1Hint 1Explore hintHide hint
Run a normal palindrome check with two pointers. What's the earliest moment you actually need your one delete?
2Hint 2Explore hintHide hint
At the first mismatch s[lo] != s[hi], a single delete can only remove s[lo] or s[hi] — deleting anything in between leaves the boundary broken.
3Hint 3Explore hintHide hint
So return isPalindrome(lo+1, hi) || isPalindrome(lo, hi-1). Use a helper that checks a fixed [lo, hi] range so no substrings are copied.
A · Core idea
March lo from the left and hi from the right. While s[lo] == s[hi], step both inward. If the pointers cross without conflict, the string was already a palindrome — return true with the delete unused. The interesting case is the first mismatch.
Why a single greedy branch is exhaustive. At the first mismatch we have s[lo] != s[hi], and everything outside [lo, hi] already matched as a mirror. Our one delete has to make [lo, hi] palindromic. Could the deleted character be some interior char s[k] with lo < k < hi? No — removing an interior char leaves s[lo] and s[hi] still sitting at the boundary, still unequal, so the range still fails. The only deletions that can possibly fix a boundary mismatch are deleting `s[lo]` or deleting `s[hi]`. That's why we check exactly two sub-ranges — [lo+1, hi] and [lo, hi-1] — and ORing them is provably complete, not a heuristic.
Why we don't pick a side cleverly. A tempting bug is to decide which end to delete based on, say, comparing s[lo+1] with s[hi]. Such heuristics break on strings like "cupucu" where local context misleads. Trying both branches costs nothing asymptotically (each is a linear scan of a shrinking range) and is bulletproof. Simplicity wins here.
Why the helper takes explicit bounds. Both branches re-verify a fixed sub-range of the original string. If the helper rebuilt substrings we'd be back to O(n) copies; instead it walks indices in place, so the whole algorithm stays O(1) space. This is the difference between the optimal and the brute force — same idea, no allocation.
Why the budget is spent at most once. After the first mismatch we either succeed (return true) or fail (return false) — we never continue the outer loop. That's the structural reason this solves the one-delete problem specifically; extending to k deletes would require recursion or DP and a fundamentally different shape.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "abca"Array state
lo=0, hi=3
a == a — match, step inward
trueC · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
A bounded edit budget localizes the decision: with one delete, the fix is pinned to the first boundary conflict, so you fork exactly once. Generalize the mental model — 'how big is the edit budget?' decides whether you greedily branch (k=1) or fall back to DP (k>1). The bounded-range palindrome helper is the reusable primitive.
ComplexityO(n) time, O(1) space — The outer scan is O(n). At most one mismatch triggers a single helper call that scans at most the remaining range — also O(n). Total O(n). Only integer indices → O(1) space.
E · Edge cases and pitfalls8s = "a" — Single char: lo(0) is not < hi(0), loop skipped → return true.Explore edge casesHide edge cases
Edge cases handled
s = "a"Single char: lo(0) is not < hi(0), loop skipped → return true.s = "aba"No mismatch ever → return true with delete unused.s = "abc"Mismatch a/c at the ends; "bc" and "ab" both fail → return false.s = "eeccccbebaeeabebccceea"Symmetric-looking trap; the two-branch check correctly returns false because neither single delete makes it a palindrome.
Pitfalls
- Choosing which side to delete by a heuristic instead of trying both — fails on adversarial inputs.
- Making the helper rebuild substrings — reintroduces O(n) space and can push time toward O(n²).
- Continuing the outer loop after a mismatch instead of returning — that would allow more than one delete.
- Forgetting the no-mismatch case returns true (zero deletes is allowed).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean validPalindrome(String s) { int lo = 0, hi = s.length() - 1; while (lo < hi) { if (s.charAt(lo) != s.charAt(hi)) { return isPalindrome(s, lo + 1, hi) || isPalindrome(s, lo, hi - 1);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Heuristic side-picking instead of trying both
Deciding which char to delete from local comparisons fails on inputs where the wrong local choice is misleading. Trying both branches is free asymptotically and always correct.
Explore the code comparisonHide the code comparison
Heuristic side-picking instead of trying both
Deciding which char to delete from local comparisons fails on inputs where the wrong local choice is misleading. Trying both branches is free asymptotically and always correct.
Don't write this
if s[lo] == s[hi - 1]:
return is_palindrome(lo, hi - 1)
else:
return is_palindrome(lo + 1, hi)Write this instead
return is_palindrome(lo + 1, hi) or is_palindrome(lo, hi - 1)2Substring copies in the helper
Slicing/concatenating to check a sub-range turns each verification into an O(n) allocation, defeating the O(1)-space goal and risking O(n²) time.
Explore the code comparisonHide the code comparison
Substring copies in the helper
Slicing/concatenating to check a sub-range turns each verification into an O(n) allocation, defeating the O(1)-space goal and risking O(n²) time.
Don't write this
boolean ok = isPalindrome(s.substring(lo + 1, hi + 1));Write this instead
boolean ok = isPalindrome(s, lo + 1, hi); // checks range in place3Spending more than one delete
If you 'skip' a char and then keep looping the outer pointers, a second mismatch could trigger a second skip — solving a different problem.
Explore the code comparisonHide the code comparison
Spending more than one delete
If you 'skip' a char and then keep looping the outer pointers, a second mismatch could trigger a second skip — solving a different problem.
Don't write this
if s[lo] != s[hi]:
lo += 1 # skip and keep going — allows multiple deletes
continueWrite this instead
if s[lo] != s[hi]:
return is_palindrome(lo + 1, hi) or is_palindrome(lo, hi - 1)Revise
Carry the pattern into the interview
Pattern to remember
Two pointers + one greedy branch on first mismatch
Code pattern to memorize
lo, hi = 0, n - 1
while lo < hi:
if s[lo] != s[hi]:
return isPalin(lo+1, hi) or isPalin(lo, hi-1) # spend the one delete
lo += 1; hi -= 1
return True # already a palindrome, no delete neededRules to remember
- 1On the first mismatch, branch: verify
s[lo+1..hi]ORs[lo..hi-1]— you have exactly one delete to spend. - 2If the pointers cross with no mismatch, it's already a palindrome → return true without using the delete.
- 3The greedy branch is provably complete: the deleted char must be one of the two mismatched ends, never an inner char.
- 4Write a clean
isPalindrome(lo, hi)helper — both branches reuse it on a fixed range, so it must take explicit bounds. - 5Don't recurse for two deletes — that's a different (harder) problem. One mismatch, one branch, done.
Use this pattern when
- Checking palindrome / symmetry with **at most one** edit (delete) allowed
- Two pointers from the ends, deciding what to do at the first conflict
- You can prove the only viable fix involves the **boundary** elements
- Need O(1) space — no copying substrings
Choose another pattern when
- Up to **k** deletes allowed → DP / recursion (Valid Palindrome III, LCS-style)
- Insertions/replacements allowed too → edit-distance DP, not greedy
- No edit budget at all → plain palindrome check (Valid Palindrome I)
- Mismatch could be fixed by an **interior** delete → greedy boundary branch is wrong
Interview takeaway
With one allowed delete, the fix must be at the boundary, so you only ever branch once: skip left or skip right and re-verify. Two pointers + a single greedy fork keeps it O(n)/O(1) — recognise this whenever an 'almost palindrome' has a tiny edit budget.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternTwo pointers with a single greedy fork on the first mismatch. Recognise it when a palindrome/symmetry check has a budget of exactly one edit — the fix is pinned to the boundary, so you branch once. Bigger budgets (k deletes) escalate to DP.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Valid PalindromeZero deletes — plain two-pointer check after filtering non-alphanumerics.
- Valid Palindrome IIIComing soonUp to k deletes — greedy breaks; use LCS/DP on the string and its reverse.
- Longest Palindromic SubstringComing soonExpand-around-center reuses the same inward two-pointer idea.
- Palindromic SubstringsComing soonCount palindromes by expanding around each center — two pointers again.