algoadvance

Given a string s, determine if it can become a palindrome after deleting at most one character from it.

Clarifying Questions

1. What characters does the string s contain?
   • The string s consists only of printable ASCII characters.
2. What is the length constraint on s?
   • The length of the string s will be at most (10^5).
3. Is the problem case-sensitive?
   • Yes, the string is case-sensitive.

Strategy

1. We will use a two-pointer approach:
   • Initialize two pointers: left pointing to the beginning of the string and right pointing to the end.
   • Move the pointers towards each other, comparing the characters at the left and right positions.
2. If the characters at left and right are the same, move both pointers inward.
3. If the characters are different, we have two options:
   • Skip the character at the left pointer and check if the resulting substring is a palindrome.
   • Skip the character at the right pointer and check if the resulting substring is a palindrome.
4. Use a helper function is_palindrome to verify if a substring is a palindrome.
5. If either possibility results in a palindrome, then the original string can be a palindrome after deleting one character.

Code

def validPalindrome(s: str) -> bool:
    def is_palindrome(sub: str, left: int, right: int) -> bool:
        while left < right:
            if sub[left] != sub[right]:
                return False
            left += 1
            right -= 1
        return True
    
    left, right = 0, len(s) - 1
    
    while left < right:
        if s[left] == s[right]:
            left += 1
            right -= 1
        else:
            # Try skipping either the left character or the right character
            return is_palindrome(s, left + 1, right) or is_palindrome(s, left, right - 1)
    
    return True

Time Complexity

• The time complexity of this approach is (O(n)), where (n) is the length of the string s. This is because, in the worst case, we might check the entire string once with two pointers and may also check one additional substring with the is_palindrome function, but overall, we are making a linear pass.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?