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!