Skip to main content

11. Valid Palindrome

easyAsked at LINE

Determine if a string is a palindrome when ignoring non-alphanumeric characters and case — LINE uses this to test two-pointer fundamentals before any chat-search problem.

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. An empty string is considered 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

Approaches

1. Clean then reverse

Filter to lowercase alphanumerics, then check the result equals its reverse.

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

Tradeoff:

2. Two pointers in place

Walk a left pointer from the start and a right pointer from the end, skip non-alphanumerics, compare lowercased characters. Avoids the temporary cleaned string.

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

Tradeoff:

LINE-specific tips

At LINE, link two pointers to scanning a chat message's normalized form for reversible search keys — concrete chat-search framing wins.

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 LINE interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →