Problem

Given a string s, determine whether it is a palindrome.

A palindrome reads the same forwards and backwards. However, there are two important rules:

  • Ignore all non-alphanumeric characters.
  • Comparison should be case-insensitive.

Example 1

Input: "Was it a car or a cat I saw?"
Output: True

After removing spaces and punctuation and converting everything to lowercase:

wasitacaroracatisaw

This reads the same from both directions.

Example 2

Input: "tab a cat"
Output: False

After cleaning the string:

tabacat

This is not a palindrome.

Intuition

The brute-force approach would be:

  1. Remove every non-alphanumeric character.
  2. Convert the string to lowercase.
  3. Compare it with its reverse.

While this works, it requires creating a new string.

Instead, we can solve it in O(1) extra space using the Two Pointer technique.

The idea is simple:

  • Start one pointer from the beginning.
  • Start another pointer from the end.
  • Skip any character that isn’t a letter or digit.
  • Compare the remaining characters (ignoring case).
  • If they don’t match, return False.
  • Otherwise, continue moving inward until the pointers meet.

Algorithm

  1. Initialize two pointers:
    • left = 0
    • right = len(s) - 1
  2. While left < right:
    • Move the left pointer until it points to an alphanumeric character.
    • Move the right pointer until it points to an alphanumeric character.
    • Compare both characters after converting them to lowercase.
    • If they differ, return False.
    • Otherwise, move both pointers inward.
  3. If every comparison matches, return True.

Python Solution

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

        while l < r:
            while l < r and not self.alphaNum(s[l]):
                l += 1

            while l < r and not self.alphaNum(s[r]):
                r -= 1

            if s[l].lower() != s[r].lower():
                return False

            l += 1
            r -= 1

        return True

    def alphaNum(self, c):
        return (
            ord("a") <= ord(c) <= ord("z") or
            ord("A") <= ord(c) <= ord("Z") or
            ord("0") <= ord(c) <= ord("9")
        )

Why Use ord()?

The helper function checks whether a character is:

  • A lowercase letter (a-z)
  • An uppercase letter (A-Z)
  • A digit (0-9)
ord("a") <= ord(c) <= ord("z")

Since ord() converts a character into its ASCII value, checking ranges becomes very efficient.

For example:

ord('A') = 65
ord('Z') = 90

ord('a') = 97
ord('z') = 122

ord('0') = 48
ord('9') = 57

Only characters within these ranges are considered valid.

Dry Run

Let’s trace the algorithm with:

"Was it a car or a cat I saw?"

Initially:

l -> 'W'
r -> '?'

The right pointer skips ? because it isn’t alphanumeric.

Now:

W == w ✓

Move inward.

Next:

a == a ✓

Continue.

Whenever a space is encountered:

" "

The pointer simply skips it.

The same happens for punctuation.

Eventually, every valid character matches, so the function returns:

True

Complexity Analysis

Time Complexity

O(n)

Each pointer moves toward the center at most once. Even though there are nested while loops, every character is visited no more than once.

Space Complexity

O(1)

No additional string is created. We only use two pointers and a few variables.

Key Takeaways

  • Two pointers are ideal when comparing elements from both ends of a sequence.
  • Skip unnecessary characters instead of building a cleaned string.
  • Convert characters to lowercase only when comparing.
  • Using ord() allows us to efficiently determine whether a character is alphanumeric without relying on built-in methods.

This is a classic interview problem because it combines string manipulation with the Two Pointer pattern while keeping both the time complexity O(n) and the space complexity O(1).