Skip to main content

125. Valid Palindrome

easy

Decide whether a string is a palindrome after removing non-alphanumeric characters and lowercasing. Classic two-pointer warm-up with a character-cleanup twist.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise.

Constraints

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

Examples

Example 1

Input
s = "A man, a plan, a canal: Panama"
Output
true

Explanation: After cleaning: "amanaplanacanalpanama" — palindrome.

Example 2

Input
s = "race a car"
Output
false

Explanation: After cleaning: "raceacar" — not a palindrome.

Example 3

Input
s = " "
Output
true

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Cleaning the string first (filter + lowercase) into a new string then comparing it to its reverse works — O(n) time, O(n) extra space.

Hint 2

Can you skip the copy and compare in place?

Hint 3

Two pointers from the ends. Skip past any non-alphanumeric character on either side. When both point at a valid character, compare lowercase. Mismatch = false; equal = advance both.

Solution approach

Reveal approach

Two-pointer in-place comparison. Left starts at 0, right at length-1. In a loop: advance left past any non-alphanumeric character; retreat right past any non-alphanumeric character. If left has crossed right, return true. Otherwise compare lowercase characters at the two positions — mismatch returns false, equal advances both pointers. O(n) time, O(1) extra space. Avoids the allocation a 'clean then compare' approach would need.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • two-pointers

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Amazon
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Valid Palindrome and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →