1. Understand the problem

• Given a string s, determine whether it is a palindrome considering only alphanumeric characters and ignoring case. Return True if it reads the same forward and backward after this normalization, otherwise False.

2. Clarify questions you would ask

1. Empty string -> palindrome (True).

2. String with only non-alphanumeric characters (e.g., “!!”) -> palindrome.

3. Mixed letters/digits (e.g., “0P” -> depending on chars, often False).

4. Case differences: treat ‘A’ and ‘a’ as equal.

5. Should we treat only ASCII alphanumerics or full Unicode letters/digits?

6. Are spaces and punctuation ignored? (Yes — ignore them.)

7. Expected time/space constraints? (Aim for O(n) time, O(1) extra space if possible.)

3. Work through examples

1. “A man, a plan, a canal: Panama” → True

2. “race a car” → False

3. ”” → True

4. ” “ → True

5. “0P” → False (because 0 != p)

6. ”., “ → True (no alphanumerics → palindrome)

7. “abba” → True

4. Brainstorm 2–3 solutions

4.1. Naive Solution

• Build a new string t by filtering s for alphanumeric characters and lowering case.

• Check t == t[::-1].

• Time: O(n) to build + O(n) to compare → O(n).

• Space: O(n) extra for t.

4.2. Two-pointer (Optimize Space)

• Use two pointers i (start) and j (end).

• Move i forward until it points to an alnum char; move j backward until it points to an alnum char.

• Compare lowercased characters; if mismatch → return False.

• Continue until i >= j → return True.

• Time: O(n) (each char visited at most once).

• Space: O(1) extra (just pointer vars)

Notes:

• Binary Search: O(logN).

• Two Pointer: O(N).

4.3. Stack

• Add all characters into a stack.

• Push all item in stack, and build a string => You will have a reverse string.

• Same with Solution 1.

• Time complexity: O(N).

• Space complexity: O(N).

5. Implement solutions

5.1. Reverse String

class Solution:
    def isPalindrome(self, s: str) -> bool:
        newStr = ''
        for c in s:
            if c.isalnum():
                newStr += c.lower()
        return newStr == newStr[::-1]

• Time complexity: O(N).

• Space complexity: O(N).

5.2. Two Pointers

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 r > l and not self.alphaNum(s[r]):
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l, r = 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'))

• Time complexity: O(N).

• Space complexity: O(1).

6. Run the testcase

Example: “A man, a plan, a canal: Panama”

• init i=0 → s[0] = ‘A’ (isalnum True).

• j = len(s)-1 → s[j] = ‘a’ (isalnum True).

• compare ‘A’.lower() vs ‘a’.lower() → ‘a’ == ‘a’ → ok. i=1, j–.

• i=1 -> ‘ ‘ (not alnum) → increment until i points to ‘m’.

• j moves left skipping punctuation, spaces, etc. Compare matching letters step by step.

• Loop finishes with i >= j → return True.