Valid Palindrome II easy

Problem Statement

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

Example 1

Input: s = "aba" Output: true

Example 2

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

Steps

The core idea is to check if the string is a palindrome or can become a palindrome by removing at most one character. We'll use two pointers (left and right) to traverse the string from both ends.

1. Two-Pointer Comparison: Iterate through the string using two pointers, one starting from the beginning and the other from the end.
2. Palindrome Check: If the characters at the left and right pointers are different, we have two options:
   • Option 1: Remove the character at the left pointer and recursively check if the remaining substring is a palindrome.
   • Option 2: Remove the character at the right pointer and recursively check if the remaining substring is a palindrome.
3. Base Case: If the pointers cross (left > right), it means we've either found a palindrome or could make it a palindrome by removing at most one character. Return True.
4. If Characters Match: If the characters at the pointers match, simply move both pointers towards the center.

Explanation

The algorithm efficiently checks for palindromes by comparing characters from both ends. If a mismatch occurs, it explores two possibilities: removing the left or right character, recursively checking if the resulting substring is a palindrome. This ensures that we only need to remove at most one character to achieve a palindrome. The base case efficiently handles the situation where a palindrome is found or can be made by removing at most one character.

Code

def validPalindrome(s):
    """
    Checks if a string can become a palindrome after deleting at most one character.

    Args:
      s: The input string.

    Returns:
      True if the string can become a palindrome after deleting at most one character, False otherwise.
    """
    left, right = 0, len(s) - 1

    def isPalindrome(s, left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    while left < right:
        if s[left] != s[right]:
            return isPalindrome(s, left + 1, right) or isPalindrome(s, left, right - 1)
        left += 1
        right -= 1
    return True

Complexity

• Time Complexity: O(N), where N is the length of the string. In the worst case, we might traverse the string a few times, but the overall complexity remains linear.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space. The recursive calls in isPalindrome do add to the call stack, but this space is proportional to the length of the string in the worst case. However, it’s not considered in the typical space complexity analysis because it’s not used to store data beyond the call stack.