DSA With AI
Week 1 ยท Two Pointers

Valid Palindrome

Check whether a string reads the same forward and backward after ignoring non-alphanumeric characters and case.

Easy Two Pointers Week 1 Practice runner

Frame the problem

  • Non-alphanumeric characters are skipped.
  • Case is ignored.
  • An empty filtered string is a palindrome.
1. Reveal example inputs and outputs

Example 1

Input:

is_palindrome("A man, a plan, a canal: Panama")

Output:

true

Example 2

Input:

is_palindrome("race a car")

Output:

false
2. Brute force first

How would filtering into a new lowercase string solve it? How can two pointers avoid that extra string?

3. Reveal the insight ladder
  1. Place one pointer at each end.
  2. Skip non-alphanumeric characters on both sides.
  3. Compare lowercase characters.
  4. Move inward until the pointers cross.
4. Dry run before code
  1. A man, a plan, a canal: Panama.
  2. Compare a with a, m with m, and keep skipping punctuation/spaces.
  3. All normalized pairs match, so return True.
5. Reveal final Python solution 
def is_palindrome(s):
    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

Complexity: Time O(n), space O(1).

Interview narration

  • I can either normalize into a new string or compare in place.
  • Two pointers preserve constant extra space.
  • Skipping happens before comparison on each side.

Common traps

  • Comparing punctuation or spaces.
  • Forgetting lowercase normalization.
  • Moving pointers incorrectly after a match.

Follow-up drills

1. When is the filtered-string approach acceptable?

It is simpler and still O(n), but uses O(n) extra space. Use it if the interviewer does not ask for constant space.

2. How would Unicode affect this?

Clarify what counts as alphanumeric and how to normalize case. Python's isalnum and lower have Unicode behavior, which may or may not match the prompt.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.