Leetcode 680. Valid Palindrome II

Problem

Leetcode 680 - Valid Palindrome II

Example:

Input: s = "aba"
Output: true

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Input: s = "abc"
Output: false

Approach

We can first check if the given string is a palindrome using a two pointer left, right where we start from left = 0, and right = len(s)-1 then we increment left and decrement right if s[left] == s[right].

If we do encounter s[left] != s[right], since we can remove at most one character from the string to be a palindrome, we chceck from left+1 to right is palindrome or left to right-1 is palindrome.

Visualization of the Approach:

s = 'abbca'
     l   r
    
Since s[left] == s[right], continue increment left and decrement right

s = 'abbca'
      l r

Since s[left] != s[right], first let's check if left+1 to right is palindrome

s[left+1: right+1]: 'bc'
                     lr
This is not a palindrome, we check if left to right-1 is palindrome

s[left: right]: 'bb'
                 lr
This is a palindrome, so we return True

Output: True

Here is the Python code for the solution:

class Solution:
    def validPalindrome(self, s:str) -> bool:
        # helper function to determine if specific area is palindrome
        def isPalindrome(left, right):
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
    
        left, right = 0, len(s)-1

        while left < right:
            if s[left] != s[right]:
                # we check if left+1 to right is palindrome or left to right-1 is palindrome
                # if either one of them is palindrome, we can return True since we just removed 1 character at most
                return isPalindrome(left+1, right) or isPalindrome(left, right-1)
            left += 1
            right -= 1

        return True    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$