How do you check a palindrome in O(1) space?

Put one pointer at each end and walk them toward each other, comparing as you go. Skip non-alphanumeric characters by advancing the relevant pointer without comparing. Building a filtered copy of the string first is easier to write but costs O(n) space.

Why do the skip loops need a bounds check?

Because a string made entirely of punctuation would run a pointer past the end of the string. Each inner while loop needs l less than r in its condition, not just the alphanumeric test.

Is an empty string a palindrome?

Yes. So is a single character, and so is a string of nothing but punctuation, since after filtering it is empty. The two-pointer loop handles all three naturally because it never enters the body.

ASAPUtils

Week 1

Valid Palindrome

Valid Palindrome with two pointers and O(1) space, with C++ and JavaScript solutions and the character filtering that makes it more fiddly than it first looks.

easy Strings Two Pointers O(n) time · O(1) space Open on LeetCode ↗

The problem

Given a string, return true if it reads the same forwards and backwards once you ignore case and skip every character that is not a letter or a digit.

"A man, a plan, a canal: Panama" -> true "race a car" -> false

Valid Palindrome

The problem

The signal

Approach ladder

1. Clean, then reverse and compare — O(n) space

2. What is it wasting?

3. Optimal — two pointers with skipping, O(1) space

Walkthrough

Complexity

Traps

Blank re-solve prompt

Related Problems