Skip to main content

18. Valid Palindrome

easyAsked at Datadog

Determine if a string is a palindrome, considering only alphanumeric characters and ignoring case. Datadog uses this as a two-pointer warmup before harder string-stream problems.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog phone screen warmup.
  • LeetCode Discuss (2025-09)— Datadog tagged.

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. Filter + reverse + compare

Filter to lowercase alphanumeric; check filtered === reversed filtered.

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: Three allocations. Datadog will push you for O(1) space.

2. Two-pointer in-place (optimal)

Pointers from both ends. Skip non-alphanumerics. Lowercase-compare; advance both. If ever unequal, return false.

Time
O(n)
Space
O(1)
function isPalindrome(s) {
  const isAlnum = c => (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
  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: O(1) extra space, single pass. The skip-then-compare pattern is the same Datadog uses for filter-then-validate over an ingestion stream.

Datadog-specific tips

Datadog grades on the in-place two-pointer approach — they'll explicitly call out 'no extra string allocation.' Articulate the skip-non-alphanumeric step before coding so the interviewer knows you have the structure in mind.

Common mistakes

  • Using s.split('').reverse() — allocates O(n) and signals you can't do it in place.
  • Forgetting case normalization — 'Aa' is a palindrome only with case-insensitive compare.
  • Treating numbers as non-alphanumeric — the problem includes digits.

Follow-up questions

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

  • Valid Palindrome II (LC 680) — allow one deletion.
  • Longest Palindromic Substring (LC 5) — different algorithm (expand-around-center).
  • Palindrome Linked List (LC 234) — same idea, harder data structure.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Is the empty string a palindrome?

Yes. The loop doesn't execute, and the function returns true. That's the correct convention.

What's 'alphanumeric'?

a-z, A-Z, 0-9. Spaces, punctuation, and symbols are skipped.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →