Valid Palindrome: Clean Two Pointer String Scanning

If you interview at Meta, Microsoft, Apple, expect some version of "Valid Palindrome". It is rated Easy, and it falls squarely into the Two Pointers pattern — pattern-first preparation beats grinding random problems every time. Part 2 of 12 in the Two Pointers arc.

The Problem

A phrase is a palindrome if, after converting to lowercase and removing all non-alphanumeric characters, it reads the same forwards and backwards. Given a string s, return True if it is a palindrome. Meta screens love this one because the clean solution avoids allocating the filtered string entirely.

Input:  s = "A man, a plan, a canal: Panama"
Output: True
"amanaplanacanalpanama" reads identically in both directions.

Recognizing the Two Pointers Pattern

Two pointers means walking a sequence with two indices that move based on a comparison — from both ends inward, or slow-and-fast in one direction. It turns brute-force pair scans that cost O(n²) into a single O(n) pass, and it is usually the intended answer whenever the input is sorted or can be sorted cheaply.

Comparing a sequence against its own reverse is the canonical ends-inward setup. The filtering requirement is a distractor — pointers can simply skip junk characters in place, which is the O(1)-space insight the interviewer is fishing for.

The Approach

Start left at 0 and right at the last index. Advance left past non-alphanumeric characters, retreat right the same way, then compare the two lowercased characters. Any mismatch ends it; pointers crossing means every meaningful pair matched.

The one-liner s2 = [c for c in s.lower() if c.isalnum()] then s2 == s2[::-1] is worth mentioning and then improving on — it costs O(n) extra space, and saying so scores points.

Python Solution

def is_palindrome(s: str) -> bool:
    """True if s is a palindrome ignoring case and non-alphanumerics."""
    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) — each character is visited at most once by either pointer
• Space: O(1) — no filtered copy is materialized

Interview Tips and Follow-Ups

• Watch the inner-loop guards: dropping left < right inside the skip loops walks off the ends on strings like "!!!". Interviewers plant that edge case.
• Know str.isalnum() — reimplementing it with ASCII ranges wastes minutes unless explicitly asked.
• The natural escalation is Valid Palindrome II (delete at most one character), covered later in this arc.

More Two Pointers problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.