Problem statement

https://leetcode.com/problems/valid-palindrome-ii/

Solution

What we need to do is to start to traverse our string from both sides and if elements are equal, we are OK, we need to take both (we can not remove both, because we allowed only delete one. There are couple of tricks we can use: all(...) to check if all elements in list are True. Also s[~i] will give you $i$-th element from the end: we traverse our string and if we have different symbols on some step, we check two options: substring s[i+1:j] and s[i:j-1].

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def validPalindrome(self, s):
        def check(i, j):
            return all(s[k] == s[j-k+i] for k in range(i, j))

        for i in range(len(s) // 2):
            if s[i] != s[~i]:
                j = len(s) - 1 - i
                return check(i+1, j) or check(i, j-1)
        return True