LeetCode #125 Easy

Valid Palindrome

Decide whether a string reads the same forwards and backwards, considering only alphanumeric characters and ignoring case.

stringtwo-pointers

Open on LeetCode ↗

02

Intuition

💡

The character class is where this one actually breaks. People write the skip as if not s[l].isalpha() and then '0P' comes back True — digits are alphanumeric and must be compared, not skipped, and isalpha silently drops them. Use isalnum. The second half of the trap is building a cleaned copy first: strip, lowercase, compare to the reverse. That is correct, but the filtering does no work the pointers cannot do in place, so it is O(n) space bought for nothing. Keep both pointers on the ORIGINAL string and, before each comparison, walk l forward and r back past anything non-alphanumeric. On 'A man, a plan, a canal: Panama' the commas are never copied anywhere, just stepped over. The invariant is that everything strictly outside l..r has already been verified to mirror.

03

Approach

1

Converge from both ends

Place l at 0 and r at the last index. A palindrome is defined by outer pairs matching, so the natural decomposition is: check the outermost pair, then reduce to the substring strictly inside it. The loop condition l < r is what encodes that reduction; when the pointers meet or cross, every pair has been checked.

2

Skip non-alphanumerics in place

Before comparing, run two small skip loops: while l < r and s[l] is not alphanumeric, advance l; likewise pull r back. This is the whole trick that removes the cleaned copy. Note both skip loops must keep the l < r guard, otherwise a string of pure punctuation would run a pointer off the end of the string.

3

Compare case-folded, and fail fast

Lowercase both characters and compare. A single mismatch is a complete counterexample, so return False immediately rather than continuing — there is nothing later in the string that can rescue it. If the loop runs to completion the string is a palindrome, so return True.

04

Solution & live demo

python

▶1class Solution:
▶2    def isPalindrome(self, s):
▶3        l, r = 0, len(s) - 1
▶4        while l < r:
▶5            if not s[l].isalnum():
▶6                l += 1
▶7                continue
▶8            if not s[r].isalnum():
▶9                r -= 1
▶10                continue
▶11            if s[l].lower() != s[r].lower():
▶12                return False
▶13            l += 1
▶14            r -= 1
▶15        return True

05

Edge cases

Empty string or a single space

The skip loops consume everything, the pointers cross without a single comparison, and the function returns True — the empty sequence is trivially a palindrome.

Digits mixed with letters, e.g. '0P'

Digits are alphanumeric so they participate; lowercasing '0' is a no-op and 'P' becomes 'p', so '0' vs 'p' correctly fails.

Odd length with a middle character

The pointers land on the same index and the loop exits, so the middle character is never compared to anything — which is correct, it mirrors itself.

A string made entirely of punctuation

The l < r guard inside each skip loop stops the pointers from running past each other, and the answer is True.

06

Complexity

Time

O(n)

Space

O(1)

Each pointer only ever moves inward, so together they touch every index at most once; no filtered copy is allocated.