Valid Palindrome I

String Simulation/Two Pointers

Problem

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

For example:

Input: "A man, a plan, a canal: Panama"
Output: true

Input: "race a car"
Output: false

Thought Process

• A palindrome is the same word spelt forwards and backwards

• We have to convert uppercase letters to lowercase and disregard spaces and special characters

Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l = 0
        r = 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

Key Points

• Two pointers approach: one starting from the beginning and one at the end

• Check whether each element is alphanumeric only, if so then convert to lowercase.

• If either element in not alphanumeric, either increment or decrement either pointer, respectively

Time Complexity

• Time: $O(n)$ where n is the number of characters in the string

• Space: $O(1)$