Skip to main content

13. Valid Palindrome

easyAsked at Notion

Determine whether a string is a palindrome after stripping non-alphanumerics and lowercasing. Notion uses this as a two-pointer warmup.

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

Source citations

Public interview reports confirming this problem appears in Notion loops.

  • Glassdoor (2026-Q1)— Notion uses this as a two-pointer string warmup.
  • LeetCode Discuss (2025)— Phone screen warmup.

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. 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

Example 2

Input
s = "race a car"
Output
false

Approaches

1. Clean and reverse

Strip non-alphanumeric, lowercase, compare to reverse.

Time
O(n)
Space
O(n)
function isPalindrome(s) {
  const t = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  return t === t.split('').reverse().join('');
}

Tradeoff: Allocates two extra strings. Works but is the 'easy' answer.

2. Two pointers with in-place filter (optimal)

Pointers from both ends. Skip non-alphanumeric. Compare lowercased characters.

Time
O(n)
Space
O(1)
function isPalindrome(s) {
  const isAN = c => /[a-z0-9]/i.test(c);
  let l = 0, r = s.length - 1;
  while (l < r) {
    while (l < r && !isAN(s[l])) l++;
    while (l < r && !isAN(s[r])) r--;
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
    l++; r--;
  }
  return true;
}

Tradeoff: Constant extra space. The two skip-loops inside the main loop are the key pattern.

Notion-specific tips

Notion grades whether you write the in-place two-pointer version. The 'clean-and-reverse' is fine for a first pass but mention the space cost and pivot to two-pointer.

Common mistakes

  • Forgetting `l < r` guard inside the inner skip loops — pointers cross.
  • Lowercasing the entire string upfront then doing two-pointer — wastes O(n) space.
  • Treating underscores or apostrophes as alphanumeric — they aren't per LC.

Follow-up questions

An interviewer at Notion may pivot to one of these next:

  • Valid Palindrome II (LC 680) — allow one deletion.
  • Longest palindromic substring (LC 5).
  • Generalize to Unicode — what's 'alphanumeric' in UTF-8?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why two pointers over reverse-and-compare?

O(1) space, early exit on first mismatch, no allocation.

Is the empty string a palindrome?

Yes — vacuously. After stripping non-alphanumeric, length 0 trivially equals its reverse.

Practice these live with InterviewChamp.AI

Drill Valid Palindrome and other Notion interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →