Skip to main content

5. Valid Palindrome

easyAsked at JetBrains

Check whether a sanitized string reads identically forward and backward — JetBrains uses this to gauge two-pointer discipline before deeper string-scanning problems.

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

Problem

Given a string s, return true if it is a palindrome after converting all uppercase letters to lowercase and removing all non-alphanumeric characters. Otherwise return false.

Constraints

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII

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 then reverse

Strip non-alphanumerics, lowercase, then compare with reversed copy.

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

Tradeoff:

2. Two pointers in place

Skip non-alphanumerics on both ends and compare. No extra allocation, matches JetBrains's preference for cursor-style string scanners.

Time
O(n)
Space
O(1)
function isPalindrome(s) {
  const ok = c => /[a-z0-9]/i.test(c);
  let l = 0, r = s.length - 1;
  while (l < r) {
    while (l < r && !ok(s[l])) l++;
    while (l < r && !ok(s[r])) r--;
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
    l++; r--;
  }
  return true;
}

Tradeoff:

JetBrains-specific tips

JetBrains expects you to avoid the allocation; mention how their lexer reads from a CharSequence cursor without materializing intermediate strings.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →