Valid Palindrome II

Free walkthrough Updated Nov 19, 2026 · 5 min read
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

    Deleting the c in abca leaves aba, a palindrome; no single deletion fixes abc.
    Deleting the c in abca leaves aba, a palindrome; no single deletion fixes abc.
    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

    1. Exactly one deletion, or at most one? (Here: at most one, so palindromes return true.)
    2. Case and punctuation: should "A man, a plan" ignore case and non-letters? (Here: no, plain lowercase.)
    3. Do you need which character to delete, or just true/false? (Here: just the answer.)
    4. 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

    In deeabeed the outer three pairs match; at the first mismatch, skipping either a or b leaves a one-letter middle, which is a palindrome.
    In deeabeed the outer three pairs match; at the first mismatch, skipping either a or b leaves a one-letter middle, which is a palindrome.

    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

    In cbbcc the first mismatch is b versus c; skipping the left character leaves bc, but skipping the right one leaves bb, so the answer is true.
    In cbbcc the first mismatch is b versus c; skipping the left character leaves bc, but skipping the right one leaves bb, so the answer is true.

    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

    1. Why is it enough to look only at the first mismatch?
    2. What changes if up to k deletions are allowed? What's the complexity?
    3. How would you return the position of the character to delete?
    4. How would you handle mixed case, spaces and punctuation?
    5. The string is a stream you can read only once from left to right. Can you still answer?
    6. Why does slicing in Python change the space complexity, and how do you avoid it?

    Related