Valid Palindrome - A Warm Up

Checking whether a string is a palindrome—ignoring punctuation, spaces, and case—is a classic coding interview warm‑up. It’s directly applicable to real‑world tasks like validating user input, detecting symmetric patterns in data, or preprocessing text for search features.

Problem Statement

Given a string s, return True if it reads the same forward and backward after removing all non‑alphanumeric characters and converting uppercase letters to lowercase. Otherwise, return False.

1. Clarify Requirements Before Jumping Into Code

I need to confirm a few points up front

Only letters and digits count; everything else should be ignored
Comparison is case‑insensitive, so convert all letters to lowercase
Should an empty or all‑punctuation string return True? Yes, treat it as a valid palindrome
Aim for O(n) time; extra O(n) space is acceptable but O(1) would be better

2. Identify the Category of the Question

This is primarily a string manipulation problem using a two‑pointer or filter‑and‑compare pattern. It combines text cleaning (filtering out unwanted characters) with a classic palindrome check that often uses two indices moving inward from both ends.

3. Consider a Brute‑Force Approach to Understand the Problem

The simplest approach is:

Build a new string by scanning s and keeping only alphanumeric lowercase characters
Create its reverse
Compare the filtered string to its reverse

That runs in O(n) time but uses O(n) extra space for the filtered and reversed strings. It’s conceptually easy but not optimal in space.

4. Brainstorm More Solutions

Two‑pointer in place: keep left and right indices on the original string, skip non‑alphanumeric, compare characters, O(n) time, O(1) extra space
Recursion: not ideal here due to call‑stack overhead
Combining filter with two‑pointer: prefilter into a list, then two‑pointer on that list

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Filter + Reverse	O(n)	O(n)	Very simple to implement	Uses extra O(n) space
Two‑Pointer In Place	O(n)	O(1)	Space‑efficient, optimal	Slightly more index logic
Prefilter + Two‑Pointer	O(n)	O(n)	Clear separation of steps	Still uses extra O(n) space

Two‑pointer in place wins on space without sacrificing time.

6. Write Pseudocode to Structure Your Thoughts

function isPalindrome(s):
  left = 0
  right = length(s) - 1

  while left < right:
    while left < right and s[left] is not alphanumeric:
      left += 1
    while left < right and s[right] is not alphanumeric:
      right -= 1
    if lowercase(s[left]) != lowercase(s[right]):
      return False
    left += 1
    right -= 1

  return True

7. Consider Edge Cases

Empty string → returns True
String of only punctuation or spaces → returns True
Single character → returns True
Two‑character mismatch (e.g., “ab”) → returns False
Mixed alphanumeric, e.g., “0P” → returns False because ‘0’ != ‘p’

8. Write Full Code Syntax

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

9. Test Your Code

assert is_palindrome("A man, a plan, a canal: Panama") == True
assert is_palindrome("race a car") == False
assert is_palindrome("") == True
assert is_palindrome(".,") == True
assert is_palindrome("0P") == False

print("All tests passed!")

10. Key Lessons to Remember for Future Questions

Two‑pointer is ideal for any “compare ends” pattern in strings or arrays
Filtering on the fly avoids building large temporary structures when space matters
Always handle non‑alphanumeric and case‑insensitive rules before comparing
Quick edge‑case checks for empty or trivial inputs can save time
Pseudocode clarifies index movement logic before coding
Communicating each decision shows structured problem‑solving skills

Happy Coding!