Skip to content
Optimal Lab

Two Pointers · 007Easy

Valid Palindrome

Given a string s, return true if it is a palindrome after converting all uppercase letters to lowercase and removing every non-alphanumeric character.

Constraints

  • 1 <= s.length <= 2 * 10^5
  • s consists of printable ASCII characters.

Examples

isPalindrome("A man, a plan, a canal: Panama")  ->  true
isPalindrome("race a car")                      ->  false
isPalindrome(" ")                               ->  true   // empty after cleaning
isPalindrome("a")                               ->  true   // single character
isPalindrome(".,")                              ->  true   // no alphanumeric characters at all
isPalindrome("0P")                              ->  false   // '0' and 'p' are both alphanumeric, but differ

Edge cases

  • A string with no alphanumeric characters is a palindrome.
  • Mixed case.
  • Digits count as alphanumeric.
Show the target complexity (spoiler)
Naive
O(n) time, O(n) space — build a cleaned string, then compare it to its reverse.
Target
O(n) time, O(1) space — two pointers walking inward, skipping non-alphanumeric characters in place.

Solve it

By hand, in your editor. The runner checks answers and timing.

git clone https://github.com/sarmadkung/optimal-round
cd optimal-round
# open problems/02-two-pointers/007-valid-palindrome.js
./practice c 007
Open the file on GitHub ↗

Stuck? Watch the pattern run

Interactive sessionTwo pointers: most water →