Valid Palindrome — Two Pointer Skip Non-Alphanumeric [Meta Easy]

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1

Input:  s = "A man, a plan, a canal: Panama"
Output: true
Explanation: After cleaning → "amanaplanacanalpanama" — reads same forwards and backwards.

Example 2

Input:  s = "race a car"
Output: false
Explanation: After cleaning → "raceacar" — not a palindrome.

Example 3

Input:  s = " "
Output: true
Explanation: After removing non-alphanumeric characters, the empty string "" is a palindrome.

Constraints: 1 <= s.length <= 2 * 10⁵. s consists only of printable ASCII characters.

• Why This Problem Matters
• Two Approaches
• Approach 1 — Clean String (Simple, O(n) Space)
• Approach 2 — In-Place Two Pointers (Optimal, O(1) Space)
• The Two-Pointer Walk
• Visual Dry Run
• Common Mistakes
• Mistake 1 — Forgetting to Lowercase Before Comparing
• Mistake 2 — Incorrect Alphanumeric Check
• Mistake 3 — Missing the Bounds Guard Inside Skip Loops
• Mistake 4 — Not Handling the Empty / All-Punctuation Case
• Solutions
• Python — Clean String
• Python — Two Pointers (O(1) Space)
• JavaScript — Clean String
• JavaScript — Two Pointers (O(1) Space)
• Complexity Analysis
• Follow-Up Questions
• LC 680 — Valid Palindrome II (Medium)
• LC 5 — Longest Palindromic Substring (Medium)
• LC 647 — Palindromic Substrings (Medium)
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

Valid Palindrome is LeetCode problem 125, and for good reason it sits at the very beginning of most curated FAANG study lists. Every company — Meta, Google, Amazon, Apple, Microsoft — uses some variation of the palindrome check in phone screens and onsite rounds. The reason is not difficulty. The reason is signal.

In about 15 lines of code, the interviewer learns whether you:

1. Read constraint text carefully — "only alphanumeric" and "ignore case" are not details to skim; they are the entire problem.
2. Know the two-pointer pattern — the foundational technique that appears in dozens of medium and hard problems.
3. Think about space — the naive solution creates a brand-new filtered string; the optimal solution runs in O(1) extra space.
4. Handle edge cases — empty strings, all-punctuation strings, single characters, strings with only digits.

Beyond the interview, this problem is the entry point into a whole family of palindrome problems. Once you internalize the "two pointers moving inward" mental model here, you will find LC 680 (delete one character), LC 5 (longest palindromic substring), and LC 647 (count palindromic substrings) dramatically easier. The two-pointer palindrome walk is always the same — what changes is what you do when pointers disagree.

Two Approaches

Approach 1 — Clean String (Simple, O(n) Space)

The most readable solution is to build a cleaned version of the string first — keep only alphanumeric characters and convert everything to lowercase — then simply check if it equals its reverse.

Steps:

1. Iterate through s, keeping only characters where c.isalnum() is true, converting each to lowercase.
2. Compare the resulting list (or string) to its reverse.

filtered = [c.lower() for c in s if c.isalnum()]
return filtered == filtered[::-1]

Why it works: By stripping everything irrelevant upfront, you reduce a complicated problem to the simplest possible palindrome check.

Trade-off: This allocates a new array or string proportional to the length of the input — O(n) extra space. In most production code that is perfectly fine. In interviews, the follow-up question "can you do it without extra space?" points directly to Approach 2.

Approach 2 — In-Place Two Pointers (Optimal, O(1) Space)

Instead of creating a cleaned copy, place one pointer at the left end of the original string and one at the right end. Walk them toward each other, skipping any character that is not alphanumeric, and compare the alphanumeric characters you do land on.

Steps:

1. Set left = 0, right = len(s) - 1.
2. While left < right:
   • Advance left while s[left] is not alphanumeric.
   • Retreat right while s[right] is not alphanumeric.
   • If both are still within bounds and s[left].lower() != s[right].lower(), return False.
   • Otherwise move both pointers inward: left += 1, right -= 1.
3. Return True.

Why it works: Both pointers will always land on exactly the characters that matter — the alphanumeric ones — in the same order they appear in the cleaned string. The non-alphanumeric characters are harmlessly leaped over.

Trade-off: Slightly more code to write, but no extra memory allocation. Time is still O(n) because each character is visited at most once by either pointer.

The Two-Pointer Walk

Let's be precise about what each step does:

left  →→→→   (moves right, skipping non-alnum)
right ←←←←   (moves left,  skipping non-alnum)

At every iteration:

• Skip phase on the left: while left < right and not s[left].isalnum(): left += 1
  • The left < right guard prevents left from shooting past right when the tail of the string is all punctuation.
• Skip phase on the right: while left < right and not s[right].isalnum(): right -= 1
  • Same guard applies.
• Compare phase: if s[left].lower() != s[right].lower(): return False
  • .lower() normalizes case. Comparing 'A' and 'a' without lowercasing would incorrectly return False.
• Advance: left += 1; right -= 1

When left >= right, every meaningful character pair has been validated. Return True.

Why the guard left < right inside the skip loops matters: Imagine the input ",./". Every character is non-alphanumeric. Without the guard, the left pointer keeps incrementing until it blows past the right pointer. With the guard, both inner loops stop before that happens, we never enter the compare phase (since left >= right), and we correctly return True — an empty-after-cleaning string is a palindrome.

Visual Dry Run

Input: "A man, a plan, a canal: Panama"

After conceptual cleaning this is "amanaplanacanalpanama", which is 20 characters. Let's trace the two-pointer approach on the original string.

s = "A man, a plan, a canal: Panama"
     0123456789...

Every comparison succeeds. The commas, spaces, and colon are silently skipped. Final result: true.

Contrast with "race a car":

s = "race a car"

The mismatch at e vs a is caught immediately.

Common Mistakes

Mistake 1 — Forgetting to Lowercase Before Comparing

# WRONG: 'A' != 'a' even though they should be treated equal
if s[left] != s[right]:
    return False

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

The problem explicitly says "ignore cases." A capital 'A' and lowercase 'a' are equal for our purposes, but a direct character comparison (==) is case-sensitive in every language. Always normalize to the same case before comparing.

Mistake 2 — Incorrect Alphanumeric Check

# WRONG: checks only letters, misses digits like '1', '2', '3'
if not s[left].isalpha():
    left += 1

# CORRECT: checks letters AND digits
if not s[left].isalnum():
    left += 1

The problem says "alphanumeric" — that includes digits 0–9. Using .isalpha() would incorrectly skip digit characters that should be included in the palindrome check.

Mistake 3 — Missing the Bounds Guard Inside Skip Loops

# WRONG: no guard — left can overshoot right on all-punctuation input
while not s[left].isalnum():
    left += 1

# CORRECT: always guard the inner loops
while left < right and not s[left].isalnum():
    left += 1

Without left < right inside the skip loop, an input like ",.," — where every character is punctuation — will cause left to run off the end of the string (or past right), causing an index error or incorrect behavior.

Mistake 4 — Not Handling the Empty / All-Punctuation Case

After cleaning, an empty string is a valid palindrome. Many implementations forget this and return False for " " or "...". The two-pointer approach handles this correctly because when the loops terminate with left >= right, we return True — we never found a mismatch. The clean-string approach handles it correctly too, because "" == ""[::-1] is True. Just make sure you are not short-circuiting early with an incorrect empty-string check.

Solutions

Python — Clean String

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Build a filtered list of lowercase alphanumeric characters
        filtered = [c.lower() for c in s if c.isalnum()]
        # A palindrome reads the same forwards and backwards
        return filtered == filtered[::-1]

Time: O(n) — one pass to filter, one pass to reverse-compare.
Space: O(n) — the filtered list uses extra memory proportional to the input.

Python — Two Pointers (O(1) Space)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            # Skip non-alphanumeric from the left
            while left < right and not s[left].isalnum():
                left += 1
            # Skip non-alphanumeric from the right
            while left < right and not s[right].isalnum():
                right -= 1

            # Compare case-insensitively
            if s[left].lower() != s[right].lower():
                return False

            # Move both pointers inward
            left += 1
            right -= 1

        # All alphanumeric character pairs matched
        return True

Time: O(n) — each character is visited at most once.
Space: O(1) — only two integer pointers, no extra data structures.

JavaScript — Clean String

function isPalindrome(s) {
  // Remove non-alphanumeric characters and lowercase everything in one regex step
  const clean = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  // Compare against the reversed version
  return clean === clean.split('').reverse().join('');
}

Time: O(n). Space: O(n) for the cleaned string.

JavaScript — Two Pointers (O(1) Space)

function isPalindrome(s) {
  // Helper: returns true if character is alphanumeric
  const isAlnum = (c) => /[a-zA-Z0-9]/.test(c);

  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    // Skip non-alphanumeric from the left
    while (left < right && !isAlnum(s[left])) left++;
    // Skip non-alphanumeric from the right
    while (left < right && !isAlnum(s[right])) right--;

    // Case-insensitive comparison
    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

Time: O(n). Space: O(1).

Complexity Analysis

Both approaches make at most one pass through the string. The two-pointer version is preferred in interviews when the interviewer asks for the optimal solution, because it avoids the hidden allocation cost of building the filtered string.

Follow-Up Questions

LC 680 — Valid Palindrome II (Medium)

Problem: Given a string s, return true if it can be a palindrome after deleting at most one character.

Key insight: Run the standard two-pointer walk. The moment you hit a mismatch at s[left] != s[right], you have exactly one deletion to spend. Use it on either the left character or the right character — check if the substring s[left+1..right] is a palindrome, or if s[left..right-1] is a palindrome. If either is true, return True.

def validPalindrome(s: str) -> bool:
    def is_palindrome(lo, hi):
        while lo < hi:
            if s[lo] != s[hi]:
                return False
            lo += 1; hi -= 1
        return True

    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            # Try skipping left char OR right char
            return is_palindrome(left + 1, right) or is_palindrome(left, right - 1)
        left += 1; right -= 1
    return True

LC 5 — Longest Palindromic Substring (Medium)

Problem: Return the longest palindromic substring in s.

Key insight: Instead of checking from the outside in, expand outward from every possible center. A palindrome has either one center character (odd length) or two center characters (even length). For each of the 2n - 1 possible centers, expand left and right while characters match, track the longest expansion found.

This is still fundamentally a two-pointer technique — the pointers just move outward instead of inward.

Time: O(n²). Space: O(1).

LC 647 — Palindromic Substrings (Medium)

Problem: Return the count of palindromic substrings in s.

Key insight: Same expand-around-center idea as LC 5, but instead of tracking the maximum, increment a counter each time the expansion succeeds. For a string of length n, there are n odd-length centers and n-1 even-length centers to try.

Time: O(n²). Space: O(1).

This Pattern Solves

The two-pointer inward walk used in Valid Palindrome is the same skeleton that powers:

• Two Sum (sorted array) — converge from both ends based on sum comparison.
• Container With Most Water (LC 11) — move the shorter side inward to find the maximum area.
• Three Sum (LC 15) — fix one element, then use two-pointer on the remaining sorted subarray.
• Trapping Rain Water (LC 42) — maintain left-max and right-max while converging.
• Valid Palindrome II (LC 680) — same walk, one allowed mismatch.
• Reverse a String / Reverse Words — place-swap with two pointers.

The common thread: you have two ends of some structure, you want to compare or process them together, and moving inward guarantees you cover every pair exactly once.

Key Takeaway

Valid Palindrome teaches you the most versatile string pattern in technical interviews: place one pointer at each end, skip anything irrelevant, compare what remains, and converge inward. Master the O(1)-space two-pointer version — not just the clean-string shortcut — because interviewers will ask for it, and more importantly, because every harder palindrome problem (LC 680, LC 5, LC 647) is a direct extension of this exact walk.