Valid Palindrome II
On this page
Problem statement
Given a string, return true if it can be made into a palindrome by deleting at most one character. A palindrome reads the same forwards and backwards. A string that is already a palindrome counts as true.
A short problem with a sharp edge: the obvious fix tries one side of the first mismatch and forgets the other. It's a favourite warm-up for checking whether you can reason about exactly where a choice happens. Original problem: LeetCode 680.
Example

Input: "abca"
Output: true # delete 'c' (or 'b') to get "aba" / "aca"
Input: "abc"
Output: false
Constraints (assumed)
- 1 ≤ length ≤ 100,000.
- Lowercase English letters.
What this question tests
- Using two pointers from both ends on a string.
- Seeing that the only decision happens at the first mismatch, and that both choices must be checked.
- Keeping it O(n) instead of trying every deletion.
Questions to ask first
- Exactly one deletion, or at most one? (Here: at most one, so palindromes return true.)
- Case and punctuation: should "A man, a plan" ignore case and non-letters? (Here: no, plain lowercase.)
- Do you need which character to delete, or just true/false? (Here: just the answer.)
- What about k deletions? Worth asking only if the interviewer hints at a follow-up; it changes the solution.
Try it first
Before reading on, try it yourself: walk inward from both ends. When the characters first disagree, what are your options, and how much of the string still needs checking? Sketch the idea and its complexity, then open the solution.
Approach ladder
Weaktry deleting every character
For each position, build the string without it and check whether it's a palindrome. That's n candidates, each O(n) to build and check: O(n²). It works for short strings and clearly fails at 10⁵.
Goodtwo pointers, but skip only one side
Move inward until the first mismatch, then skip the left character and check the rest. It's O(n) and passes many tests, but it's wrong: sometimes only skipping the right character works (see the common bug). This is the answer interviewers most often see, and they will test it.
Strongtwo pointers, check both options at the first mismatch
Everything outside the first mismatch already matches, so the only question is which of the two mismatched characters to delete. Check s[l+1..r] and s[l..r−1]; if either is a palindrome, the answer is true. Two linear scans at most: O(n) time, O(1) space.
Solution
Step 1: move inward while the ends match

Start with l = 0 and r = n − 1. While s[l] == s[r], move both inward. If they cross, the string is already a palindrome.
Step 2: at the first mismatch, try both deletions
The characters outside [l, r] already pair up, so a single deletion must remove s[l] or s[r]. Check whether s[l+1..r] or s[l..r−1] reads the same both ways.
def valid_palindrome(s):
def is_pal(i, j):
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
return is_pal(i + 1, j) or is_pal(i, j - 1)
i += 1
j -= 1
return True
boolean validPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return isPal(s, i + 1, j) || isPal(s, i, j - 1);
}
i++;
j--;
}
return true;
}
private boolean isPal(String s, int i, int j) {
while (i < j) {
if (s.charAt(i++) != s.charAt(j--)) return false;
}
return true;
}
bool isPal(const string& s, int i, int j) {
while (i < j) {
if (s[i] != s[j]) return false;
i++; j--;
}
return true;
}
bool validPalindrome(const string& s) {
int i = 0, j = (int)s.size() - 1;
while (i < j) {
if (s[i] != s[j]) return isPal(s, i + 1, j) || isPal(s, i, j - 1);
i++; j--;
}
return true;
}
func isPal(s string, i, j int) bool {
for i < j {
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
func validPalindrome(s string) bool {
i, j := 0, len(s)-1
for i < j {
if s[i] != s[j] {
return isPal(s, i+1, j) || isPal(s, i, j-1)
}
i++
j--
}
return true
}
Time: O(n): the outer walk plus at most two checks of the remaining middle. Space: O(1); pass indices instead of slicing, since slices copy the string.
The common bug

Checking only one side of the mismatch. In "cbbcc", the ends c/c match, then s[1] = 'b' and s[3] = 'c' differ. Skipping the left leaves "bc" (not a palindrome), and a one-sided solution returns false. Skipping the right leaves "bb", so the correct answer is true. Always try both.
A second slip is building substrings like s[i+1:j+1] and reversing them: correct, but each costs O(n) extra memory. Index-based checks keep space O(1).
Edge cases
- Empty or one character: true.
- Already a palindrome:
"aba"→ true without any deletion. - Two characters: always true (delete either).
- Mismatch near the ends (
"abcdba") vs. in the middle ("abccxba"): the same logic handles both. - Both options valid: fine; return true on the first.
Variants seen in interviews
- Valid Palindrome (no deletions, ignore case and non-alphanumerics): skip non-letters with the pointers. See Valid Palindrome.
- At most k deletions: the "try both" branching explodes; use DP on the longest palindromic subsequence (deletions needed = n − LPS), O(n²).
- Return the index to delete, or −1: same algorithm, return which side worked.
- Minimum insertions to make a palindrome: also n − LPS.
- Palindrome linked list: find the middle, reverse the second half, compare.
Follow-up questions
- Why is it enough to look only at the first mismatch?
- What changes if up to k deletions are allowed? What's the complexity?
- How would you return the position of the character to delete?
- How would you handle mixed case, spaces and punctuation?
- The string is a stream you can read only once from left to right. Can you still answer?
- Why does slicing in Python change the space complexity, and how do you avoid it?
Related
- Patterns: Two Pointers
- Similar problems: Valid Palindrome, Longest Palindromic Substring, Palindrome Partitioning, Container With Most Water
- Data structures: Arrays and Strings