Valid Palindrome II

EasyProblemExternal linkUpdated Oct 25, 2026

Description

Given a string s, determine whether you can make it a palindrome by removing at most one character from it.

A palindrome is a word that reads the same forwards and backwards. For example, "aba" and "racecar" are palindromes, while "abc" is not.

Your task is to return true if the string is already a palindrome, or if it becomes one after deleting exactly one character. Return false if even removing one character cannot produce a palindrome.

Examples

Example 1

Input: s = "aba"

Output: true

Explanation: The string "aba" is already a palindrome — it reads the same from left to right as from right to left. No deletion is needed, so the answer is true.

Example 2

Input: s = "abca"

Output: true

Explanation: The string "abca" is not a palindrome as-is. However, if we delete the character 'c' at index 2, we get "aba", which is a palindrome. Since we only needed one deletion, the answer is true.

Example 3

Input: s = "abc"

Output: false

Explanation: No single deletion can turn "abc" into a palindrome. Removing 'a' gives "bc" (not a palindrome), removing 'b' gives "ac" (not a palindrome), and removing 'c' gives "ab" (not a palindrome). The answer is false.

Constraints

1 ≤ s.length ≤ 10^5
s consists of lowercase English letters

Editorial

Brute Force

Intuition

The most direct way to solve this is to try every possible deletion. We know the string can have at most one character removed. So, for each position in the string, we can remove the character at that position, build the resulting string, and check if it is a palindrome.

If the original string is already a palindrome, we return true immediately. Otherwise, we try removing the character at index 0, then index 1, then index 2, and so on — checking each time whether the shortened string reads the same forwards and backwards.

Think of it like editing a word on paper: you cover up one letter at a time with your finger and read what remains. If any single cover-up produces a palindrome, the answer is yes.

Step-by-Step Explanation

Let's trace through with s = "abca":

Step 1: First, check if "abca" is already a palindrome.

Compare s[0]='a' with s[3]='a' → match
Compare s[1]='b' with s[2]='c' → mismatch
"abca" is NOT a palindrome. We must try deletions.

Step 2: Try removing index 0. Remaining string = "bca".

Compare 'b' with 'a' → mismatch. Not a palindrome.

Step 3: Try removing index 1. Remaining string = "aca".

Compare 'a' with 'a' → match
Middle character 'c' is fine (single center).
"aca" IS a palindrome!

Step 4: Since we found a single deletion that produces a palindrome, return true.

(In the worst case we would try all n deletions before concluding.)

Brute Force — Try Every Single Deletion — Watch how we remove one character at a time and check if the remaining string is a palindrome, iterating through all positions until a valid deletion is found.

Algorithm

Check if the string s is already a palindrome. If yes, return true.
For each index i from 0 to n-1:
a. Build a new string by removing the character at index i
b. Check if this new string is a palindrome
c. If it is, return true
If no single deletion produces a palindrome, return false

Code

class Solution {
public:
    bool isPalindrome(const string& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }

    bool validPalindrome(string s) {
        if (isPalindrome(s)) return true;
        for (int i = 0; i < s.size(); i++) {
            string modified = s.substr(0, i) + s.substr(i + 1);
            if (isPalindrome(modified)) return true;
        }
        return false;
    }
};

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(text: str) -> bool:
            return text == text[::-1]

        if is_palindrome(s):
            return True

        for i in range(len(s)):
            modified = s[:i] + s[i + 1:]
            if is_palindrome(modified):
                return True

        return False

class Solution {
    private boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }

    public boolean validPalindrome(String s) {
        if (isPalindrome(s)) return true;
        for (int i = 0; i < s.length(); i++) {
            String modified = s.substring(0, i) + s.substring(i + 1);
            if (isPalindrome(modified)) return true;
        }
        return false;
    }
}

var validPalindrome = function(s) {
    const isPalindrome = text => text === text.split("").reverse().join("");

    if (isPalindrome(s)) return true;

    for (let i = 0; i < s.length; i++) {
        const modified = s.slice(0, i) + s.slice(i + 1);
        if (isPalindrome(modified)) return true;
    }

    return false;
};

Complexity Analysis

Time Complexity: O(n²)

We try up to n deletions. For each deletion, we build a new string of length n-1 in O(n) time and check if it is a palindrome in O(n) time. So the total work is n × O(n) = O(n²).

Space Complexity: O(n)

Each time we build the modified string, it takes O(n) space. Only one modified string exists at a time, so the extra space is O(n).

Why This Approach Is Not Efficient

The brute force approach runs in O(n²) time. With n up to 10^5, that means up to 10^10 operations — far too slow for typical time limits of 1-2 seconds.

The core waste is that we treat every position as equally likely to be the character that needs deletion. But think about it: if the string is "almost" a palindrome, the problematic character must be near the point where the palindrome property first breaks. We do not need to try deleting characters at positions far from the mismatch.

The key insight: if we use two pointers converging from both ends and they first disagree at positions left and right, then the only characters worth deleting are s[left] or s[right]. No other deletion can fix the mismatch. This reduces the problem from trying n deletions to trying at most 2.

Optimal Approach - Two Pointers with Greedy Skip

Intuition

Start two pointers at the beginning and end of the string, moving them toward each other. As long as the characters at both pointers match, we shrink the window inward — these matching outer characters are already palindromic and need no deletion.

The interesting moment comes when we hit the first mismatch at positions left and right. At this point, we know that at least one of these two characters must be removed for the string to possibly be a palindrome. We have exactly two choices:

Skip the left character: Check if the substring from left+1 to right is a palindrome.
Skip the right character: Check if the substring from left to right-1 is a palindrome.

If either option gives a palindrome, the answer is true. If neither works, no single deletion can save the string.

Think of it like two people reading the same book — one from the front, one from the back. They compare pages as they go. When they first disagree, one of them skips their page and they check if the rest still matches. If skipping one person's page works, the book is "almost" the same from both directions.

Step-by-Step Explanation

Let's trace through with s = "abca":

Step 1: Initialize two pointers: left = 0, right = 3.

Step 2: Compare s[0] = 'a' with s[3] = 'a'. They match! Move pointers inward: left = 1, right = 2.

Step 3: Compare s[1] = 'b' with s[2] = 'c'. Mismatch! We have found the first disagreement. We now have two choices to try.

Step 4: Choice 1 — skip the left character. Check if s[2..2] = "c" is a palindrome. A single character is always a palindrome. ✓

Step 5: Since Choice 1 succeeds, we do not even need to try Choice 2. The substring from left+1 to right is a palindrome, which means deleting s[left] = 'b' makes the whole string a palindrome.

Step 6: Return true.

Let's also trace a failing case, s = "abc":

Step 7: left = 0, right = 2. Compare s[0] = 'a' with s[2] = 'c'. Mismatch on the very first comparison.

Step 8: Choice 1 — skip left: check s[1..2] = "bc". Is 'b' == 'c'? No. Not a palindrome.

Step 9: Choice 2 — skip right: check s[0..1] = "ab". Is 'a' == 'b'? No. Not a palindrome.

Step 10: Neither choice works. Return false.

Two Pointers with Greedy Skip — Valid Palindrome II — Watch how two pointers converge from both ends. On the first mismatch, we try skipping one character from either side and check if the remaining substring is a palindrome.

Algorithm

Define a helper function isPalindrome(s, left, right) that checks whether the substring s[left..right] is a palindrome using two pointers.
Initialize two pointers: left = 0, right = s.length - 1.
While left < right:
a. If s[left] == s[right], move both pointers inward (left++, right--).
b. If s[left] != s[right], we have a mismatch. Try two options:
- Check if s[left+1..right] is a palindrome (skip left character)
- Check if s[left..right-1] is a palindrome (skip right character)
- Return true if either option is a palindrome; otherwise return false.
If the loop completes without mismatch, the string is already a palindrome — return true.

Code

class Solution {
public:
    bool checkPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }

    bool validPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                // Try skipping left or skipping right
                return checkPalindrome(s, left + 1, right) ||
                       checkPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }
};

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def check_palindrome(left: int, right: int) -> bool:
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                # Try skipping left character or right character
                return check_palindrome(left + 1, right) or check_palindrome(left, right - 1)
            left += 1
            right -= 1
        return True

class Solution {
    private boolean checkPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }

    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                // Try skipping left or skipping right
                return checkPalindrome(s, left + 1, right) ||
                       checkPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }
}

var validPalindrome = function(s) {
    const checkPalindrome = (left, right) => {
        while (left < right) {
            if (s[left] !== s[right]) return false;
            left++;
            right--;
        }
        return true;
    };

    let left = 0, right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) {
            // Try skipping left character or right character
            return checkPalindrome(left + 1, right) || checkPalindrome(left, right - 1);
        }
        left++;
        right--;
    }
    return true;
};

Complexity Analysis

Time Complexity: O(n)

The main two-pointer pass traverses the string from both ends toward the center, performing at most n/2 comparisons. When a mismatch is found, the helper function checkPalindrome checks a substring that is at most n-2 characters long, also in O(n). So the total work is O(n) + O(n) = O(n). We never revisit characters or perform nested iterations.

Space Complexity: O(1)

We only use a constant number of integer variables (left, right pointers). No additional strings or data structures are created — the helper function works on the original string using index bounds. This is a significant improvement over the brute force, which required O(n) space for building modified strings.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Trying only the left deletion. return check_palindrome(left + 1, right)

On s = "aab" it returns false; the answer is true. A mismatch says one of the two letters has to go, but not which one. Here deleting the left one, the first a, leaves "ab"; deleting the right one, the b, leaves "aa". Try both: check_palindrome(left + 1, right) or check_palindrome(left, right - 1).

Choosing the side by peeking at the next letter. elif s[left + 1] == s[right]:

On s = "abbab" it returns false; the answer is true. At the mismatch both deletions can look right. The first a and the last b differ; deleting the a pairs b with b, so this code deletes it, but further in a b meets an a and no deletion is left. Deleting the last b instead leaves "abba". One peeked letter can't tell which deletion works; checking the rest of the string both ways can.

Letting every recursive call delete again. return self.validPalindrome(s[left + 1:right + 1]) or self.validPalindrome(s[left:right])

On s = "abcd" it returns true; the answer is false. Calling validPalindrome again on the shorter string gives that call a deletion of its own, so the code allows as many deletions as it likes, and with enough deletions any string becomes a palindrome. After the one deletion, the rest must already be a palindrome: check it with a plain loop that deletes nothing.

Where This Pattern Is Taught

This problem practises opposite-direction two pointers that compare from both ends. It's taught in Introduction to Two Pointers, which covers the one-deletion twist: at the first mismatch only two deletions are possible, so check the rest both ways.