Leetcode 680: Valid Palindrome II

The original question can be found here.

The question is asking if a string is palindromic if at most 1 character can be removed from string. Let’s look at an example:

abcgegba
  ^  ^
  L  R

Let’s say we still use the 2 pointers apporach as mentioned in Valid Palaindrome question. Once we find a difference, we know that we have to remove one of those chars. But which one shall we remove? Does it even matter?

If we look carefully into the example, we find that the removed character matters. Let’s say we remove character c, then the remaining string abgegba is a valid palindrome. However, if we remove character g, the remaining string abcgeba won’t be valid. What shall we do in this case?

Since we don’t know which one to remove, we try both. In this example, we try to verify "abgegba" and "abcgeba". As long as one of the strings is valid, we know the input string is a valid palindrome:

class Solution:
    def validPalindrome(self, s: str) -> bool:
        left, right = self.find_difference(s, 0, len(s) - 1)
        if left >= right:
            return True
        return self.is_palindromic(s, left + 1, right) or self.is_palindromic(s, left, right - 1)
        
    def is_palindromic(self, s: str, left: int, right: int) -> bool:
        left, right = self.find_difference(s, left, right)
        return left >= right
    
    def find_difference(self, s: str, left: int, right: int) -> (int, int):
        while left < right:
            if s[left] != s[right]:
                break
            left += 1
            right -= 1
        return (left, right)

Time complexity: O(n). Space complexity: O(1).