125. Valid Palindrome

Q: Why is Valid Palindrome considered an IBM staple?

Public IBM interview reports list it among the top-3 string-screener questions because it has a clean two-pointer optimal, a tempting O(n)-space first answer, and natural follow-ups (Valid Palindrome II, longest palindromic substring) for the next round.

Q: Is the empty string a palindrome?

Yes, per the LeetCode spec — and IBM interviewers expect you to explicitly state that an empty (or all-symbols) input returns true before submitting. Forgetting the edge case is the most common single point-deduction on this problem.

easyAsked at IBM

Valid Palindrome is IBM's go-to string-parsing screener. The bar is whether you can articulate the two-pointer in-place approach, handle non-alphanumeric characters in the spec, and avoid the O(n) extra-space trap of building a normalized copy.

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

Source citations

Public interview reports confirming this problem appears in IBM loops.

Glassdoor (2026-Q1)— Appears in IBM cloud-engineering and SWE-1 phone-screen reports.
LeetCode (2026-Q1)— Tagged under IBM company frequency (top 50).
GeeksforGeeks (2025-11)— Cited in IBM interview-experience archive.

Problem

A phrase is a palindrome if, after converting all uppercase letters to lowercase 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

Explanation: After cleaning: 'amanaplanacanalpanama' reads the same both ways.

Example 2

Input

s = "race a car"

Output

false

Explanation: 'raceacar' is not a palindrome.

Example 3

Input

s = " "

Output

true

Explanation: Empty string after cleaning is trivially a palindrome.

Approaches

1. Normalize then reverse-compare

Filter to alphanumeric lowercase, then compare the cleaned string against its reverse.

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

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

Tradeoff: Concise and readable — fine to mention as a first pass — but allocates O(n) intermediate strings. The interviewer will ask you to do it in O(1) extra space.

2. Two pointers in place (optimal)

Move left from start and right from end, skipping non-alphanumeric characters. Compare lowercase forms.

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

function isAlphanumeric(ch) {
  return /^[a-z0-9]$/i.test(ch);
}

function isPalindrome(s) {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    while (left < right && !isAlphanumeric(s[left])) left++;
    while (left < right && !isAlphanumeric(s[right])) right--;
    if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
    left++;
    right--;
  }
  return true;
}

Tradeoff: O(1) space and a single pass. Watch the inner-loop bound check (`left < right`) — without it, an all-symbols string sends the pointers past each other and you index out of range.

IBM-specific tips

IBM screens for two things on this problem: (1) you confirm 'alphanumeric only, case-insensitive' before coding — never assume the cleaning rules — and (2) you propose the two-pointer in-place version. Candidates who only ship the regex-clean version get a 'meets bar but did not demonstrate space optimization' note. Always verify the empty-string and single-char cases verbally before submitting.

Common mistakes

Forgetting the `left < right` guard inside the skip loops — pointers cross and you compare bogus characters.
Treating underscore or hyphen as alphanumeric (the spec says alphanumeric only — letters + digits).
Skipping the lowercase conversion on one side of the comparison.
Building the cleaned string when the interviewer asked for O(1) extra space.

Follow-up questions

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

Valid Palindrome II — allow deleting at most one character (LeetCode 680).
Longest Palindromic Substring (LeetCode 5).
Palindrome Partitioning — return all possible palindrome partitions (LeetCode 131).
What if the input is a Unicode string? How do letters with accents map?

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 is Valid Palindrome considered an IBM staple?

Public IBM interview reports list it among the top-3 string-screener questions because it has a clean two-pointer optimal, a tempting O(n)-space first answer, and natural follow-ups (Valid Palindrome II, longest palindromic substring) for the next round.

Is the empty string a palindrome?

Yes, per the LeetCode spec — and IBM interviewers expect you to explicitly state that an empty (or all-symbols) input returns true before submitting. Forgetting the edge case is the most common single point-deduction on this problem.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →