Skip to main content

17. Valid Palindrome

easyAsked at Lyft

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

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

Problem

Given a string s, determine if it's a palindrome considering only alphanumeric characters and ignoring case. Return true if it reads the same forwards and backwards.

Constraints

  • 1 <= s.length <= 2*10^5
  • s consists 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 + reverse

Strip non-alphanumeric and lowercase, compare with reverse.

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

Tradeoff:

2. Two pointer in place

Advance left/right pointers while skipping non-alphanumerics; compare characters.

Time
O(n)
Space
O(1)
function isPalindrome(s) {
  const isAN = c => /[a-zA-Z0-9]/.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:

Lyft-specific tips

Lyft will ask which approach uses less memory — bonus signal goes to candidates who notice the two-pointer version avoids allocating the cleaned string copy.

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 Lyft interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →