Valid Palindrome II
Decide whether a string becomes a palindrome after deleting at most one character, by trying both deletions only at the first mismatch.
Problem Understanding
Valid Palindrome II: return true if s can be a palindrome after deleting at most one character.
Examples: "aba" is already a palindrome; "abca" becomes "aba" or "aca" by deleting one character; "abc" cannot be fixed with one deletion.
The Intuition: Spend the Deletion at the First Mismatch
Check from the outside in, as in Valid Palindrome, with two pointers l and r. While s[l] == s[r], those characters are fine and both pointers move inward.
At the first mismatch, one of s[l] or s[r] must be the extra character, since every pair outside already matches. So there are only two candidates:
- Delete
s[l]: iss[l+1..r]a palindrome? - Delete
s[r]: iss[l..r−1]a palindrome?
If either is, return true. If the pointers meet without a mismatch, no deletion was needed.
Interactive Walkthrough
Matched pairs are shaded from the outside in. At the first mismatch, watch each deletion get checked in turn: the deleted character is struck through and the rest is compared from both ends.
Dry Run Table
Input: "abca"
| l | r | Compare | Action |
|---|---|---|---|
| 0 | 3 | a = a | move in |
| 1 | 2 | b ≠ c | first mismatch |
| — | — | delete b: "c" | palindrome |
Return true.
The Solution Template
Two pointers, with a palindrome check for each possible deletion.
Valid Palindrome II Code
1var validPalindrome = function(s) {2 const isPal = (l, r) => {3 while (l < r) {4 if (s[l++] !== s[r--]) return false;5 }6 return true;7 };8 let l = 0, r = s.length - 1;9 while (l < r) {10 if (s[l] !== s[r]) return isPal(l + 1, r) || isPal(l, r - 1);11 l++;12 r--;13 }14 return true;15};
Edge Cases & Common Mistakes
- Already a palindrome: no deletion needed; return true.
- Trying only one side: "eeeed" fails if you only delete the left character; check both.
- Allowing more than one deletion: once you are inside a check, any further mismatch means false.
- Re-checking the whole string: only the part between l and r needs checking after the first mismatch.
Summary
Move two pointers inward while the ends match. At the first mismatch, the deleted character must be s[l] or s[r], so return whether s[l+1..r] or s[l..r−1] is a palindrome. If there is no mismatch, return true. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet