We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Valid Palindrome II

Number: 680

Difficulty: Easy

Paid? No

Companies: Meta, Yandex, Amazon, Google, Fortinet, Microsoft, Apple, TikTok, Uber, Adobe, Yahoo

Problem Description

Given a string s, determine if it can become a palindrome after deleting at most one character. In other words, return true if by removing up to one character from s, the resulting string reads the same forwards and backwards, otherwise return false.

Key Insights

  • Use two pointers starting from the beginning and end of the string.
  • Compare characters; if they match, move both pointers inward.
  • When a mismatch is found, you have two possibilities: skip the left character or the right character.
  • Check if either of the resulting substrings is a palindrome.
  • The approach effectively leverages a greedy method and operates in linear time.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), using only constant extra space.

Solution

The solution uses a two-pointer technique—one pointer starts at the beginning of the string and another at the end. They move towards each other while comparing characters. If a mismatch occurs, the algorithm tries skipping either the left or right character and then checks if the remaining substring forms a palindrome. This additional check is done using a helper function that verifies if a given substring is a palindrome. This strategy ensures that the algorithm only allows one deletion, conforming to the constraint.

Code Solutions

# Define the Solution class
class Solution:
    def validPalindrome(self, s: str) -> bool:
        # Helper function to check if the substring s[left:right+1] is a palindrome.
        def isPalindromeRange(left, right):
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
        
        # Initialize two pointers.
        left, right = 0, len(s) - 1
        
        # Use two pointers to compare characters from both ends.
        while left < right:
            # If characters don't match, try skipping one character
            if s[left] != s[right]:
                # Check if either skipping the left or the right character results in a palindrome.
                return isPalindromeRange(left + 1, right) or isPalindromeRange(left, right - 1)
            left += 1
            right -= 1
        return True
← Back to All Questions