Valid Palindrome — The Two Pointer Gateway Problem at Meta and Microsoft

Problem Statement#

Given a string s, return true if it is a palindrome after lowercasing all letters and removing every non-alphanumeric character, otherwise return false.

Constraints:

• 1 <= s.length <= 2 * 10^5
• s consists only of printable ASCII characters

Input:  s = "A man, a plan, a canal: Panama"
Output: true

Input:  s = "race a car"
Output: false

Why This Problem Matters#

LeetCode 125 Valid Palindrome is the single most common two pointer warm-up question at FAANG. Meta uses it as a 10 minute opener in phone screens, Microsoft uses it to test in-place character handling, and Amazon uses it to gauge how cleanly a candidate writes guard conditions. The problem is rated Easy on LeetCode, but the optimal in-place version separates candidates who memorized solutions from those who actually understand the two pointer technique.

The naive solution builds a cleaned copy of the string and reverses it, costing O(n) extra space. The two pointer technique walks both ends inward, skipping non-alphanumeric characters in place, and uses only O(1) extra space. Interviewers explicitly listen for the in-place version once you produce the naive one.

This problem is also the gateway to harder palindrome variants like LC 5 Longest Palindromic Substring, LC 680 Valid Palindrome II (one deletion allowed), and LC 9 Palindrome Number. Internalize the convergence pattern here and the harder problems unfold quickly.

The Core Insight#

A palindrome reads the same forwards and backwards, so any two characters equidistant from the center must match. Two pointers, one starting at the left end and one at the right end, can verify that property by walking inward and comparing.

Non-alphanumeric characters are the only complication. Rather than building a cleaned copy of the string, we skip them in place: if the left pointer is on a non-alphanumeric character, increment it; if the right pointer is on one, decrement it. Once both pointers land on alphanumerics, compare them after lowercasing.

The invariant is straightforward: when the loop exits, every alphanumeric pair from the outside in has been compared and matched. If any comparison failed, we return false immediately.

Visual Dry Run#

For input s = "A man, a plan, a canal: Panama":

Solution (Optimal)#

class Solution:
    def isPalindrome(self, 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

var isPalindrome = function(s) {
    const isAlnum = c => /[a-z0-9]/i.test(c);
    let left = 0;
    let right = s.length - 1;
    while (left < right) {
        while (left < right && !isAlnum(s[left])) left++;
        while (left < right && !isAlnum(s[right])) right--;
        if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
        left++;
        right--;
    }
    return true;
};

Time: O(n) — each character is visited at most once by either pointer Space: O(1) — only the two pointers, no extra buffer

Common Mistakes#

• Building a cleaned, lowercased copy of the string before checking, which costs O(n) extra space
• Forgetting the inner left < right guard in the skip loops, causing pointers to cross past each other
• Comparing characters without lowercasing, which fails on inputs like "Aa"
• Using isalpha instead of isalnum and missing digit-containing palindromes like "0P"
• Treating empty strings or single characters as edge cases when the loop already handles them

Interview Tips#

• Lead with the brute force: "I could clean and reverse, but that costs O(n) space, so let me show the two pointer in-place version"
• Walk through one example on the whiteboard with both pointers drawn as arrows
• Mention the Unicode caveat: isalnum and lower behavior on non-ASCII input may need clarification
• After the solution, offer the LC 680 follow-up unprompted to demonstrate pattern fluency

Follow-up Questions#

• What if one character can be deleted? (Hint: LC 680, two pointer with a single skip allowed)
• How would you find the longest palindromic substring? (Hint: LC 5, expand-around-center)
• What if the string is given as a stream and you cannot index from both ends? (Hint: reverse and compare, O(n) space)
• Can you solve this for a singly linked list? (Hint: LC 234, slow-fast pointers and reverse second half)

Key Takeaways#

• LeetCode 125 Valid Palindrome is rated Easy and is the most common two pointer warm-up at Meta, Microsoft, and Amazon
• Optimal solution uses opposite-end two pointers walking inward with O(n) time and O(1) space
• Skip non-alphanumeric characters in place rather than building a cleaned copy of the string
• Always include the left < right guard in skip loops to prevent pointer crossing
• This problem is the gateway to LC 5, LC 680, and LC 234 palindrome variants
• Interviewers explicitly listen for the in-place O(1) space version after the naive solution
• Lowercase only at comparison time, never mutate the input string