LeetEye LeetEye
Easy Two Pointers ~5 min

Valid Palindrome

two-pointers valid-palindrome

Problem

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.

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

Examples

Example 1
Input: s = "A man, a plan, a canal: Panama"
Output: true
"amanaplanacanalpanama" is a palindrome
Example 2
Input: s = "race a car"
Output: false
"raceacar" is not a palindrome
Example 3
Input: s = " "
Output: true
Empty string after removing non-alphanumeric = palindrome
Key Insight

Compare characters from both ends, moving inward.

Palindrome check = two pointers from ends moving inward, comparing cleaned characters.

How to Approach This Problem

Pattern Recognition: When you see keywords like valid palindrome two-pointers, think Two Pointers.

Step-by-Step Reasoning

1 What must be true for a string to be a palindrome?
Answer: Characters at position i equal characters at position (n-1-i)
Position 0 must equal position n-1, position 1 must equal position n-2, etc. Mirror symmetry.
2 Why use two pointers instead of creating a reversed copy?
Answer: Two pointers use O(1) space vs O(n) for reverse
Reversing creates a new string (O(n) space). Two pointers compare in-place.
3 If s[left] == s[right], what do you do?
Answer: Move left pointer right AND right pointer left
Characters match, move inward to check the next pair.
4 When left pointer is at a space or punctuation:
Answer: Skip it by moving left pointer right
Non-alphanumeric chars don't count. Skip them without comparison.
5 When do the pointers stop moving?
Answer: When left >= right
When pointers cross or meet, we've checked all pairs. If no mismatch found, it's a palindrome.
6 If s[left] ≠ s[right] (after skipping non-alphanumeric and case conversion):
Answer: Return false immediately
A single mismatch proves it's not a palindrome. Early exit.

Solution

def isPalindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric from left
        while left < right and not s[left].isalnum():
            left += 1
        # Skip non-alphanumeric from right
        while left < right and not s[right].isalnum():
            right -= 1
        
        # Compare characters (case-insensitive)
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Two Pointers problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye