Skip to main content

17. Valid Palindrome

easyAsked at Snowflake

Determine whether a string is a palindrome considering only alphanumeric characters. Snowflake uses this to test two-pointer hygiene and Unicode-aware normalization — the same normalization pipeline that runs before COLLATE comparisons in their SQL engine.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team screens used this as warm-up before COLLATE follow-up.
  • LeetCode Discuss (2025-09)— Reported at Snowflake SDE-I phone screens.

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

Explanation: After filtering, empty string is a palindrome.

Approaches

1. Filter then reverse

Build a normalized string of lowercase alphanumeric chars; compare with its reverse.

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

Tradeoff: Allocates two extra strings. Works but uses O(n) extra space.

2. Two-pointer in-place (optimal)

Left pointer from start, right from end. Skip non-alphanumeric. Compare case-insensitively. Stop when pointers cross.

Time
O(n)
Space
O(1)
function isPalindrome(s) {
  function isAlnum(c) {
    return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
  }
  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: Linear, O(1) extra space. Skips filtered chars in-place — the pattern used in string normalization pipelines.

Snowflake-specific tips

Snowflake interviewers grade this on whether you handle the case-insensitive compare AND alphanumeric skip in the same two-pointer loop, instead of doing two passes. Bonus signal: discuss Unicode — for real COLLATE, you'd need NFC normalization plus locale-aware comparison; ASCII is just the warm-up.

Common mistakes

  • Calling toLowerCase on the whole string up front, paying O(n) extra allocation.
  • Forgetting that digits count as alphanumeric.
  • Not advancing both pointers after a match — infinite loop.

Follow-up questions

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

  • Valid Palindrome II (LC 680) — allow at most one removal.
  • How would you handle Unicode-aware comparison?
  • What's the COLLATE clause for in Snowflake SQL?

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 instead of filter-then-reverse?

It avoids the O(n) extra allocation. On a 200K-char input that matters for cache behavior.

What changes for Unicode?

You need normalization (NFC), then locale-aware folding, then comparison. ASCII is the trivial case where char + 32 = lowercase. Snowflake's COLLATE clause handles this with ICU under the hood.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →