680.Valid_Palindrome_II(Easy).md

680. Valid Palindrome II (Medium)

Date and Time: Nov 22, 2024, 14:44 (EST)

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

Question:

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"

Output: true

Example 2:

Input: s = "abca"

Output: true

Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"

Output: false

Constraints:

• 1 <= s.length <= 10^5

• s consists of lowercase English letters.

Walk-through:

Use two pointers l, r to compare two chars and find where they are different. Then, we check the rest of the palindrome s[l+1:r], s[l, r-1] (same as removing the left char, the right char) is valid or not. If one of them is valid, then we know s is valid.

Python Solution:

class Solution:
    def validPalindrome(self, s: str) -> bool:
        # Use two ptrs to compare chars
        # Then check two scenario: 1. remove the left char, l += 1. 2. remove the right char, r -= 1

        # TC: O(n), n = len(s), SC: O(1)
        # Check if we have valid palindrome
        def palindrome(l, r):
            while l < r:
                if s[l] != s[r]:
                    return False
                l, r = l+1, r-1
            return True

        l, r = 0, len(s)-1
        while l < r:
            # Try increment l or decrement r
            if s[l] != s[r]:
                return palindrome(l+1, r) or palindrome(l, r-1)
            l, r = l+1, r-1
        return True

Time Complexity: $O(n)$
Space Complexity: $O(1)$