Two Pointers: Valid Palindrome II

You are given a string s. Return true if s can be a palindrome after deleting at most one character. A palindrome reads the same forward and backward. The string already contains only alphanumeric characters.

Answer

We use two pointers combined with the trivial slicing method.

The first time we see a mismatch, we create two substrings: one skipping the left character and one skipping the right character. We then check (using [::-1]) whether either one is a palindrome. If yes, return True.

If pointers match normally, simply move them inward.

Python
class Solution:
    def validPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1

        while l < r:
            if s[l] != s[r]:
                skipL = s[l + 1 : r + 1]
                skipR = s[l : r]
                return skipL == skipL[::-1] or skipR == skipR[::-1]
            else:
                l += 1
                r -= 1

        return True

Time complexity: \(O(n)\). Optimal.

Space complexity: \(O(n)\) due to substring creation. Suboptimal.

Programming lesson: The first if is (usually, as I am seeing) used to handle the “bad” case, i.e., the one situation that breaks the pattern. Once that case is handled, the else or the rest describes what to do in the “good” case.

Back to collection