Skip to main content

18. Valid Palindrome

easyAsked at Spotify

Determine if a string is a palindrome considering only alphanumeric characters case-insensitively.

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

Problem

Given a string s, return true if it is a palindrome after converting all uppercase letters into lowercase and removing all non-alphanumeric characters.

Constraints

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

Normalize to lowercase alphanumeric and compare with its 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

Move inward skipping non-alphanumeric. Compare lowercased chars in place — zero extra string allocations.

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

Tradeoff:

Spotify-specific tips

Spotify cares about string-normalization discipline because search and lyric-matching pipelines run very similar in-place character filters on millions of queries per day.

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

Practice these live with InterviewChamp.AI →