Valid Palindrome

PracticeNeetCode ↗LeetCode ↗

Given a string s, determine whether it reads the same forward and backward once you lowercase it and strip out everything that isn't a letter or digit.

Example

Key Pointers

• Two pointers closing in from both ends is the natural fit — no need to build a cleaned copy of the string first.
• Skip non-alphanumeric characters by advancing a pointer past them before comparing anything.
• Compare lowercased characters so case differences never cause a false mismatch.

Step-by-Step Analysis

1. Set left = 0, right = len(s) - 1.
2. While left < right: advance left past any non-alphanumeric character, and pull right back past any non-alphanumeric character.
3. Compare s[left].lower() to s[right].lower() — if they differ, return False.
4. Move left forward and right backward, and repeat until the pointers meet; return True.

Complexity

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

Code

def isPalindrome(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

Code Explanation

How the solution above works, piece by piece.

1. left, right = 0, len(s) - 1: compare from both ends toward the middle; no cleaned copy of the string is built, so O(1) extra space.
2. The two inner while loops skip anything that isn't a letter or digit (isalnum()): spaces, punctuation. The left < right guard stops them running past each other.
3. s[left].lower() != s[right].lower(): compare ignoring case. One mismatch means it can't be a palindrome.
4. Otherwise move both pointers inward and repeat.
5. When the pointers meet, every pair matched → True. Each character is visited once: O(n).

Visual Walkthrough

Running it on s = "Was it a car or a cat I saw?":

Video Explanation

NeetCode — LeetCode 125