Skip to main content
CodePeetCodePeet
CodePeet 250

Valid Palindrome II

EASYProblemSolveExternal Links

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

  1. Check if the string s is already a palindrome. If yes, return true.
  2. 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
  3. 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;
    }
}

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:

  1. Skip the left character: Check if the substring from left+1 to right is a palindrome.
  2. 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

  1. Define a helper function isPalindrome(s, left, right) that checks whether the substring s[left..right] is a palindrome using two pointers.
  2. Initialize two pointers: left = 0, right = s.length - 1.
  3. 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.
  4. 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;
    }
}

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.