18. Valid Palindrome

Q: Why two pointers and not reverse?

Two pointers is O(1) extra space. Reverse allocates an O(n) string. For 200k characters that matters.

Q: Empty string?

True by convention — a palindrome of length 0 is trivially equal to its reverse.

easyAsked at Workday

Determine whether a string is a palindrome considering only alphanumeric characters and ignoring case. Workday uses this to evaluate two-pointer fluency on cleaned input — same pattern as normalizing employee-ID strings during reconciliation.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

Glassdoor (2025-Q4)— Workday SDE1 phone screen.

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.

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

Approaches

1. Clean + reverse compare

Strip non-alphanumeric, lowercase, compare with reverse.

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

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

Tradeoff: O(n) extra space. Works but allocates two intermediate strings.

2. Two pointers in place

Pointers from both ends. Skip non-alphanumeric. Compare lowercased values.

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: O(1) space. The inner while loops are bounded by the outer i < j check — total work is still O(n).

Workday-specific tips

Workday grades for the i < j guards inside the inner skip-loops — without them, the pointers can cross and you'll read garbage. Mention this guard explicitly. The all-non-alphanumeric edge case (e.g., ' ') is also a frequent gotcha.

Common mistakes

Forgetting i < j guards in the inner skip-loops — pointers cross.
Comparing s[i] === s[j] without lowercasing first.
Returning false on the empty-after-cleaning case — should be true.

Follow-up questions

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

Valid Palindrome II (LC 680) — allow removing one character.
Longest Palindromic Substring (LC 5).
What if Unicode characters with combining marks matter?

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 pointers and not reverse?

Two pointers is O(1) extra space. Reverse allocates an O(n) string. For 200k characters that matters.

Empty string?

True by convention — a palindrome of length 0 is trivially equal to its reverse.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →