Valid Palindrome

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───

Problem

• A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.
• Note: Alphanumeric characters consist of letters (A-Z, a-z) and numbers (0-9).

Solution

• Naïve solution would be check if the string is equal to the string reversed, but this would add space complexity.
• Instead, we can keep a pointer at the start and at the end of the string, if they aren’t the same character, return False.
  • This would work for simple strings, but it doesn’t cover the case-insensitive and non-alphanumeric character cases.
  • Instead, we can increment/decrement the left/right if either side is not alphanumeric, then we check the .lower() of both strings

class Solution:
    def isPalindrome(self, s: str) -> bool:
	    # time complexity: O(n)
	    # space complexity: O(1)
 
        l, r = 0, len(s) - 1
 
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
                
            while l < r and not s[r].isalnum():
                r -= 1
                
            if s[l].lower() != s[r].lower():
                return False
 
            l += 1
            r -= 1
 
        return True

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───