Skip to main content

18. Valid Palindrome

easyAsked at Expedia

Check if a string is a palindrome considering only alphanumeric characters.

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

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 then reverse

Strip non-alphanumeric, lowercase, compare with reverse.

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

Tradeoff:

2. Two pointers in place

Move pointers inward, skip non-alnum. Expedia uses similar logic to canonicalize destination strings for fuzzy match.

Time
O(n)
Space
O(1)
function isPalindrome(s) {
  s = s.toLowerCase();
  const isAlnum = c => /[a-z0-9]/.test(c);
  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] !== s[r]) return false;
    l++; r--;
  }
  return true;
}

Tradeoff:

Expedia-specific tips

Expedia interviewers prefer the in-place two-pointer version; mention how the technique applies to canonicalizing user-typed destination queries before search.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →