Valid Palindrome II

Q: What is the best time complexity for Valid Palindrome II?

Optimal (two pointers, branch once) runs in O(n) time and O(1) extra space. One inward scan plus at most two more linear checks.

Q: Which pattern does Valid Palindrome II use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Q: Is there a brute force solution for Valid Palindrome II?

Yes. Brute force (try every removal) takes O(n²) time and O(1) space. Check the string as is, then try removing each index one at a time and check whether what remains is a palindrome.

Q: Which edge cases should I test for Valid Palindrome II?

The string is already a palindrome: zero removals is allowed; A single character or two different characters (always true); At the first mismatch, only one of the two possible removals works; Two separate mismatches: needs two removals, so false.

Easy Arrays & Hashing Two Pointer Original on LeetCode

Reported atMeta Apple

Valid Palindrome II is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers, branch once), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every removal) up.

Problem

Given a string s, return true if it can become a palindrome after deleting at most one character from it, and false otherwise.

A palindrome reads the same forwards and backwards. Deleting nothing is allowed, so a string that is already a palindrome counts.

Examples

Example 1

Input: s = "kayaks"
Output: true
Why: Removing the final 's' leaves "kayak", which reads the same both ways.

Example 2

Input: s = "madxam"
Output: true
Why: Removing the 'd' (or the 'x') leaves "maxam" (or "madam").

Example 3

Input: s = "stone"
Output: false
Why: No single removal turns it into a palindrome.

Constraints

1 <= s.length <= 10^5
s contains only lowercase English letters.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (try every removal)	`O(n²)`	`O(1)`
Optimal (two pointers, branch once)	`O(n)`	`O(1)`

1Brute force (try every removal)

TimeO(n²)Up to n + 1 palindrome checks, each O(n).

SpaceO(1)The check skips index k with pointers instead of building a new string.

Check the string as is, then try removing each index one at a time and check whether what remains is a palindrome.

If s is a palindrome, return true.
For each index k, check the string without s[k] using two pointers that skip k.
Return true on the first success, false otherwise.

class Solution {
    public boolean validPalindrome(String s) {
        for (int k = -1; k < s.length(); k++) {
            if (isPalWithout(s, k)) return true;
        }
        return false;
    }

    private boolean isPalWithout(String s, int skip) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (i == skip) { i++; continue; }
            if (j == skip) { j--; continue; }
            if (s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}

class Solution:
    def validPalindrome(self, s: str) -> bool:
        for k in range(-1, len(s)):
            if self.is_pal_without(s, k):
                return True
        return False

    def is_pal_without(self, s: str, skip: int) -> bool:
        i, j = 0, len(s) - 1
        while i < j:
            if i == skip:
                i += 1
                continue
            if j == skip:
                j -= 1
                continue
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

class Solution {
public:
    bool validPalindrome(string s) {
        for (int k = -1; k < (int)s.size(); k++) {
            if (isPalWithout(s, k)) return true;
        }
        return false;
    }

private:
    bool isPalWithout(const string& s, int skip) {
        int i = 0, j = (int)s.size() - 1;
        while (i < j) {
            if (i == skip) { i++; continue; }
            if (j == skip) { j--; continue; }
            if (s[i] != s[j]) return false;
            i++;
            j--;
        }
        return true;
    }
};

function validPalindrome(s) {
    for (let k = -1; k < s.length; k++) {
        if (isPalWithout(s, k)) return true;
    }
    return false;
}

function isPalWithout(s, skip) {
    let i = 0, j = s.length - 1;
    while (i < j) {
        if (i === skip) { i++; continue; }
        if (j === skip) { j--; continue; }
        if (s[i] !== s[j]) return false;
        i++;
        j--;
    }
    return true;
}

2Optimal (two pointers, branch once)

TimeO(n)One inward scan plus at most two more linear checks.

SpaceO(1)Only index variables.

Move two pointers inward while the characters match. At the first mismatch, one of the two characters has to go, so the answer is whether the inner range without the left one or without the right one is a palindrome. Each of those is a plain linear check.

i = 0, j = n - 1; while i < j and s[i] == s[j], move both inward.
If they met, return true.
Return isPal(i + 1, j) || isPal(i, j - 1).

class Solution {
    public 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;
            i++;
            j--;
        }
        return true;
    }
}

class Solution:
    def validPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return self.is_pal(s, i + 1, j) or self.is_pal(s, i, j - 1)
            i += 1
            j -= 1
        return True

    def is_pal(self, s: str, i: int, j: int) -> bool:
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

class Solution {
public:
    bool validPalindrome(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;
    }

private:
    bool isPal(const string& s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j]) return false;
            i++;
            j--;
        }
        return true;
    }
};

function validPalindrome(s) {
    let i = 0, j = s.length - 1;
    while (i < j) {
        if (s[i] !== s[j]) {
            return isPal(s, i + 1, j) || isPal(s, i, j - 1);
        }
        i++;
        j--;
    }
    return true;
}

function isPal(s, i, j) {
    while (i < j) {
        if (s[i] !== s[j]) return false;
        i++;
        j--;
    }
    return true;
}

Edge cases to test

The string is already a palindrome: zero removals is allowed
A single character or two different characters (always true)
At the first mismatch, only one of the two possible removals works
Two separate mismatches: needs two removals, so false

Hints

Hint 1

Compare characters from both ends inward. As long as they match, no removal is needed.

Hint 2

At the first mismatch s[i] != s[j], the removed character must be s[i] or s[j]. Check whether s[i+1..j] or s[i..j-1] is a palindrome.

FAQ

What is the best time complexity for Valid Palindrome II?

Optimal (two pointers, branch once) runs in O(n) time and O(1) extra space. One inward scan plus at most two more linear checks.

Which pattern does Valid Palindrome II use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Valid Palindrome II?

Yes. Brute force (try every removal) takes O(n²) time and O(1) space. Check the string as is, then try removing each index one at a time and check whether what remains is a palindrome.

Which edge cases should I test for Valid Palindrome II?

The string is already a palindrome: zero removals is allowed; A single character or two different characters (always true); At the first mismatch, only one of the two possible removals works; Two separate mismatches: needs two removals, so false.