Valid Palindrome II

NeetCode: Valid Palindrome II · LeetCode: 680. Valid Palindrome II · Difficulty: Easy

Given a string s, return true if it can be a palindrome after deleting at most one character.

Example

Text

Input:  s = "aba"     Output: true
Input:  s = "abca"    Output: true    (delete 'c' or 'b')
Input:  s = "abc"     Output: false

Brute force: try deleting every character

If s is already a palindrome the answer is true. Otherwise delete each position in turn and test whether the remaining string is a palindrome. There are n candidates and each test costs O(n), so this is quadratic.

Java

class Solution {
    private boolean isPal(String s) {
        int n = s.length();
        for (int i = 0; i < n / 2; i++) {
            if (s.charAt(i) != s.charAt(n - 1 - i)) {
                return false;
            }
        }
        return true;
    }

    public boolean validPalindrome(String s) {
        if (isPal(s)) {
            return true;
        }
        for (int skip = 0; skip < s.length(); skip++) {
            String t = new StringBuilder(s).deleteCharAt(skip).toString();
            if (isPal(t)) {
                return true;
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.validPalindrome("aba"));
        System.out.println(sol.validPalindrome("abca"));
        System.out.println(sol.validPalindrome("abc"));
        System.out.println(sol.validPalindrome(""));
    }
}

Output

true
true
false
true

Time: O(n^2). Space: O(n) for each candidate copy: new StringBuilder(s).deleteCharAt(skip) copies the string and removes one character, and deleteCharAt itself shifts the tail, so each candidate costs O(n).

Optimal: two pointers with one allowed skip

Walk inward from both ends while the characters match. At the first mismatch s[l] != s[r] one of the two must be deleted, and only those two choices can fix this position: delete s[l] (so check s[l+1..r] with both ends included) or delete s[r] (so check s[l..r-1] with both ends included). Each of those is a plain palindrome check, and after that no more deletions are allowed. If neither works, the answer is false.

Java

class Solution {
    // Checks s[l..r] with both ends inclusive; an empty range (l > r) is a palindrome.
    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;
    }

    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;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.validPalindrome("aba"));
        System.out.println(sol.validPalindrome("abca"));
        System.out.println(sol.validPalindrome("abc"));
        System.out.println(sol.validPalindrome(""));
    }
}

Output

true
true
false
true

Time: O(n): the main scan plus at most two further scans. Space: O(1). All indices are int, so r - 1 can reach -1 only when r is 0, which cannot happen here because l < r holds at the mismatch.