Valid Palindrome II

Problem#

Given a string s, return true if you can make it a palindrome by deleting at most one character.

Examples#

"aba" → true
"abca" → true (delete c or b)
"abc" → false

Constraints#

1 <= s.length <= 10^5, lowercase.

Hints#

Hint 1

Walk converging pointers. On the first mismatch you have one chance — try skipping left, or skipping right.

Approach#

Converging two pointers until a mismatch. At the mismatch, the only useful single deletion is at either end of the current window — verify that one of the two resulting substrings is a clean palindrome. A helper isPalRange(l, r) cleanly factors out the second check.

Solution#

class Solution {
public:
    bool validPalindrome(string s) {
        int l = 0, r = s.size() - 1;
        while (l < r) {
            if (s[l] != s[r]) {
                return isPal(s, l + 1, r) || isPal(s, l, r - 1);
            }
            ++l; --r;
        }
        return true;
    }
private:
    bool isPal(const string& s, int l, int r) {
        while (l < r) {
            if (s[l] != s[r]) return false;
            ++l; --r;
        }
        return true;
    }
};

func validPalindrome(s string) bool {
    isPal := func(l, r int) bool {
        for l < r {
            if s[l] != s[r] {
                return false
            }
            l++
            r--
        }
        return true
    }
    l, r := 0, len(s)-1
    for l < r {
        if s[l] != s[r] {
            return isPal(l+1, r) || isPal(l, r-1)
        }
        l++
        r--
    }
    return true
}

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

        l, r = 0, len(s) - 1
        while l < r:
            if s[l] != s[r]:
                return is_pal(l + 1, r) or is_pal(l, r - 1)
            l += 1
            r -= 1
        return True

function validPalindrome(s) {
    const isPal = (l, r) => {
        while (l < r) {
            if (s[l] !== s[r]) return false;
            l++;
            r--;
        }
        return true;
    };
    let l = 0, r = s.length - 1;
    while (l < r) {
        if (s[l] !== s[r]) {
            return isPal(l + 1, r) || isPal(l, r - 1);
        }
        l++;
        r--;
    }
    return true;
}

class Solution {
    public boolean validPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return isPal(s, l + 1, r) || isPal(s, l, r - 1);
            }
            l++;
            r--;
        }
        return true;
    }

    private boolean isPal(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

function validPalindrome(s: string): boolean {
    const isPal = (l: number, r: number): boolean => {
        while (l < r) {
            if (s[l] !== s[r]) return false;
            l++;
            r--;
        }
        return true;
    };
    let l = 0, r = s.length - 1;
    while (l < r) {
        if (s[l] !== s[r]) {
            return isPal(l + 1, r) || isPal(l, r - 1);
        }
        l++;
        r--;
    }
    return true;
}

Editorial#

Without the “at most one deletion” rule, this is the textbook palindrome check. With one deletion allowed, the only moment a decision matters is the first mismatch — and there are only two single-deletion options (the left or the right character of the bad pair). Any other deletion either re-creates the same mismatch or is wasted on already-matching characters. Each isPal call walks at most n/2 characters, and only the first mismatch ever triggers them, so total work is still linear.

Complexity#

Time: O(n).
Space: O(1).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#