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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Valid Palindrome II

Difficulty: Easy

Problem Description

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

Key Insights

  • A palindrome reads the same forward and backward.
  • To check if a string can be a palindrome after removing one character, we can use a two-pointer approach.
  • If a mismatch is found, we can either ignore the character at the left pointer or the right pointer and check if the resulting substring is a palindrome.

Space and Time Complexity

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

Solution

We will use a two-pointer technique to check for palindromic properties. The idea is to have two pointers, one starting from the beginning of the string and the other from the end. We will compare the characters at these pointers. If they are equal, we move both pointers towards the center. If they are not equal, we have two options: skip the character at the left pointer or the right pointer and check if either resulting substring is a palindrome. We define a helper function to verify if a substring is a palindrome.

Code Solutions

def validPalindrome(s: str) -> bool:
    def is_palindrome_range(left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            # Check both possibilities: skipping left or right character
            return is_palindrome_range(left + 1, right) or is_palindrome_range(left, right - 1)
        left += 1
        right -= 1
    return True
← Back to All Questions