Two Pointers — Valid Palindrome II
↗ LeetCode: Valid Palindrome II · Easy · pattern chapter →
Given a string s, return true if it can become a palindrome by deleting at most one character.
Example 1 — s = "aba" → trueExample 2 — s = "abca" → true (delete c or b) Example 3 — s = "abc" → false
Constraints — 1 ≤ n ≤ 10⁵. Lowercase ASCII. Brute tries deleting each char and re-checks — O(n²) = 10¹⁰ ops at n=10⁵ (TLE). Two-pointer with one delete-window is O(n) = 10⁵ ops = <5 ms.
Interview timer00:00
Approach 1 — Try deleting each position
Intuition. For each i, check if s minus index i is a palindrome. Plus check the original.
boolean validPalindromeBrute(String s) {
if (isPali(s, 0, s.length() - 1)) return true;
for (int i = 0; i < s.length(); i++) {
String t = s.substring(0, i) + s.substring(i + 1);
if (isPali(t, 0, t.length() - 1)) return true;
}
return false;
}
boolean isPali(String s, int l, int r) {
while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
return true;
}Complexity — Time O(n²); Space O(n) per substring.
Approach 2 — Two pointers with one deletion budget
Insight from brute. Walk from ends. On mismatch, we have exactly two options: skip l OR skip r. Try both and return whether either remaining substring is a palindrome. Any subsequent mismatch would exceed the budget.
boolean validPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
if (s.charAt(l) != s.charAt(r))
return isPali(s, l + 1, r) || isPali(s, l, r - 1);
l++; r--;
}
return true;
}
boolean isPali(String s, int l, int r) {
while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
return true;
}Complexity — Time O(n) — each mismatch triggers at most 2 O(n) checks; Space O(1).
Approach 3 — Generalization to k deletions
Insight. For k > 1 deletions, recursion on the two options at each mismatch with memoization gives O(n · k). Equivalent to: is s k-close to a palindrome — related to LPS (Longest Palindromic Subsequence): answer yes iff n - LPS(s) ≤ k.
boolean validPalindromeK(String s, int k) {
int lps = longestPalindromicSubseq(s);
return s.length() - lps <= k;
}Complexity — Time O(n²) via LPS DP; Space O(n²) or O(n) with roll-down. Overkill for k = 1.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Try deleting each position | O(n²) | O(n) | baseline |
| Two pointers + budget | O(n) | O(1) | expected optimum |
| LPS DP for general k | O(n²) | O(n) | generalization |
When to use which
- Standard "at most 1 deletion" → two-pointer with budget.
- Larger k → LPS DP.
- "Return the resulting palindrome" → trace the branch that succeeded and construct the string.
- Case-insensitive / alphanumeric-only — see Valid Palindrome for the parsing rules.
Related problems
- Valid Palindrome — zero deletions
- Longest Palindromic Subsequence — LPS DP
- Palindromic Substrings