0680.md

680. Valid Palindrome II

Level:

Topic:

Question

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

Input: s = "aba"
Output: true

Intuition

Like checking valid palindrome but with at most one char difference.

1. use two pointers to check both end are equal
2. if all chars are equal, return true at the end
3. if there is a char is not equal, there are 2 cases
   1. remove the left char and continue to validate
   2. remove the right char and continue to validate
   3. true if either removal is valid, means either pair of pointer are >=
   • > is because that the string is even so two pointers might not be overlapping

Code

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

public boolean validPalindrome(String s) {
    // two pointer
    // if sees different char, try remove the left and continue to check
    // and try remove the right and check
    // if either returns true, it's true
    // if both returns false, it's false

    int n = s.length();
    int i = 0, j = n-1;

    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) {
            int i1 = i, j1 = j-1;
            int i2 = i+1, j2 = j;
            while (i1 < j1 && s.charAt(i1) == s.charAt(j1)) {
                i1++;
                j1--;
            }

            while (i2 < j2 && s.charAt(i2) == s.charAt(j2)) {
                i2++;
                j2--;
            }
            return i1 >= j1 || i2 >= j2;
        }
        i++;
        j--;
    }
    return true;
}