Easy

Valid Palindrome II

LAB

Return true if s can become a palindrome after deleting at most one character.

EXAMPLES

Example 1

Input
{
  "s": "aba"
}

Output
true

FUNCTION SHAPE

s: string→bool

SOLUTION NOTE

This is a slight modification to the existing algorithm. The idea is we are allowed a single mismatching pair. So we basically compare pairs until we see the first mismatch. (notice that at most 1 means we can also have no mismatches. So if the original string is just a palindrome, the algorithm will default to the same behaviour as the definition)

We have two options, either delete s[i] or s[j]. If we delete s[i] we no longer have any deletions remaining, so we just check if s[i+1:j] (inclusive) is a palindrome. Similarly for if we delete s[j]. We take the or of both cases, ie. if any of them is a palindrome, we can just delete the one that leads to a palindrome.

Reveal reference solution +

pythonREFERENCE

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

    n = len(s)
    i = 0
    j = n-1
    while i < j:
        if s[i] != s[j]:
            return isPalindrome(i+1, j) or isPalindrome(i, j-1)
        i += 1
        j -= 1
    return True

TimeO(n)

SpaceO(1)

Open on LeetCode ↗