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

Difficulty: Easy

Problem Description

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Given a string s, return true if it is a palindrome, or false otherwise.

Key Insights

  • Ignore case sensitivity and non-alphanumeric characters.
  • Utilize a two-pointer technique to compare characters from both ends of the string.
  • An empty string after processing is considered a palindrome.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the string, as we traverse the string once. Space Complexity: O(1) - since we only use a constant amount of space for pointers.

Solution

The problem can be solved using the two-pointer technique. We can use two pointers, one starting from the beginning of the string and the other from the end. We will skip non-alphanumeric characters and compare the characters at both pointers after converting them to lowercase. If they are equal, we continue moving the pointers inward; otherwise, we return false. If we successfully compare all relevant characters, we return true.

Code Solutions

def isPalindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    
    while left < right:
        # Move left pointer to the next valid character
        while left < right and not s[left].isalnum():
            left += 1
        # Move right pointer to the previous valid character
        while left < right and not s[right].isalnum():
            right -= 1
        
        # Compare characters in a case-insensitive manner
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True
← Back to All Questions