Skip to main content

125. Valid Palindrome

easyAsked at Airbnb

After lowercasing and removing non-alphanumeric chars, is the string a palindrome? Airbnb asks this to test two-pointer-in-place rather than the easier O(n) extra-space approach.

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

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

  • Glassdoor (2026-Q1)— Airbnb new-grad phone-screen reports list this as a 10-15 min warm-up.
  • Blind (2025-12)— Recurring in Airbnb new-grad onsite reports.

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

Example 3

Input
s = " "
Output
true

Approaches

1. Build cleaned copy + reverse-compare

Filter+lowercase the string, then compare with its reverse.

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

Tradeoff: Cleanest one-liner. The O(n) extra space is fine for typical inputs but misses the in-place answer.

2. Two-pointer in place (optimal)

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

Time
O(n)
Space
O(1)
function isPalindrome(s) {
  function isAlnum(c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
  }
  let l = 0, r = s.length - 1;
  while (l < r) {
    while (l < r && !isAlnum(s[l])) l++;
    while (l < r && !isAlnum(s[r])) r--;
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
    l++;
    r--;
  }
  return true;
}

Tradeoff: O(1) extra space, single pass. The inner skip loops handle non-alphanumeric without allocating a cleaned copy.

Airbnb-specific tips

Airbnb interviewers expect the O(1)-space answer. The two-pointer pattern is foundational — if you reach for the regex-cleanup approach, name the space tradeoff and then code the two-pointer. Skipping the in-place version loses the 'higher bar' signal.

Common mistakes

  • Forgetting to lowercase before comparing.
  • Including spaces or punctuation in the comparison.
  • Off-by-one on the loop (use l < r, not l <= r — at l == r there's nothing to compare).

Follow-up questions

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

  • Valid Palindrome II (LC 680): allow one deletion.
  • Valid Palindrome III (LC 1216): allow up to k deletions — DP.
  • Longest palindromic substring (LC 5) — different problem.

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-pointer when the regex version is simpler?

Same asymptotic time, O(1) vs O(n) space. For huge strings that matters. Airbnb specifically values the in-place answer as a signal of low-level fluency.

Is per-char toLowerCase inefficient?

It's O(1) per call in JavaScript. Same for the char-class check.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →