Problem Statement in English

You’re given a string s. Your task is to return whether it’s a palindrome or not. You’re only supposed to consider alphanumeric characters.

Approach

The first thing that probably occurred to you is - why not just reverse the string and compare it with the string, if they’re equal then it’s a palindrome. Well yea, but that uses extra space and time. We can do it in $O(n)$ time and $O(1)$ space.

We use the 2 Pointer Technique. Just initialise 2 pointers, l and r, at the first and last index of the string respectively. Everytime l and r point to the same character, move l one step to the right, and r one step to the left.

Solution in Python


class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1

        while l < r:
            # ignore non alphanumeric characters
            while not s[l].isalnum() and l < r:
                l += 1
            # ignore non alphanumeric characters
            while not s[r].isalnum() and l < r:
                r -= 1

            if s[l].lower() != s[r].lower():
                return False
            
            # move to the right
            l += 1
            # move to the left
            r -= 1

        return True

Complexity

  • Time: $O(n)$
    Since we process $n$ characters at most.

  • Space: $O(1)$
    Since we only store a few integer variables.

And we are done.