Valid Palindrome

Check if a string is a palindrome, considering only alphanumeric characters.

Pattern

Two Pointers Converge

This problem follows the Two Pointers Converge pattern, commonly found in the Two Pointers category. Recognizing this pattern is key to solving it efficiently in an interview setting.

Approach

How to Solve It

Use two pointers from both ends, skip non-alphanumeric, compare characters.

Key Insight

The trick is handling the 'skip non-alphanumeric' part cleanly — use inner while loops to advance past junk characters before comparing.

Step-by-step

1Initialize left pointer at index 0, right pointer at end of string
2While left < right, skip non-alphanumeric chars on both sides
3Compare lowercased characters at left and right
4If they don't match, return false immediately
5Move left forward and right backward
6If loop completes, return true — it's a palindrome

Pseudocode

left = 0, right = len(s) - 1
while left < right:
    while left < right and not isAlphanumeric(s[left]):
        left++
    while left < right and not isAlphanumeric(s[right]):
        right--
    if toLower(s[left]) != toLower(s[right]):
        return false
    left++
    right--
return true

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Master this pattern with YeetCode

Practice Valid Palindrome and similar Two Pointers problems with flashcards. Build pattern recognition through active recall.

Practice this problem

NextTwo Sum II →