17. Valid Palindrome

Q: What if the string is empty after filtering?

Treat it as a palindrome (vacuously true). The two-pointer loop never executes, so the early-return is implicit.

Q: Why two pointers over reverse?

No allocation, and you bail on the first mismatch — important for huge strings where most non-palindromes fail in the first few chars.

easyAsked at Plaid

Determine if a string is a palindrome after removing non-alphanumerics and lowercasing. Plaid asks this as a string-normalization warm-up before harder merchant-name canonicalization problems.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Plaid loops.

Glassdoor (2025)— Plaid SWE I OA — palindrome with normalization.
LeetCode Discuss (2026)— Plaid intro.

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

Approaches

1. Normalize, reverse, compare

Filter, lowercase, then check normalized === normalized.reverse().

Time: O(n)
Space: O(n)

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

Tradeoff: Readable but allocates two extra strings.

2. Two-pointer in-place

Pointers from both ends. Skip non-alphanumerics. Compare characters lowercased.

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: No allocation. Cleaner for very long strings. The 'skip non-alnum' inner loops keep the pointers moving toward the middle.

Plaid-specific tips

Plaid grades this on whether you handle the normalization step explicitly. Bonus signal: ask whether to skip whitespace AND punctuation, or just whitespace. Their merchant-canonicalization treats 'AMZN MKT' and 'amzn-mkt' as equivalent — this primitive is the building block.

Common mistakes

Forgetting to lowercase before comparing.
Using a regex inside the loop without anchoring — can match unexpected characters.
Off-by-one when both pointers land on the same non-alnum and never advance.

Follow-up questions

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

Allow up to k character deletions and still be a palindrome.
Find the longest palindromic substring (LC 5).
Normalize merchant names for fuzzy matching — same pattern, broader equivalence rules.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What if the string is empty after filtering?

Treat it as a palindrome (vacuously true). The two-pointer loop never executes, so the early-return is implicit.

Why two pointers over reverse?

No allocation, and you bail on the first mismatch — important for huge strings where most non-palindromes fail in the first few chars.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →