Palindrome Check

Given a string s, return true if it is a palindrome, and false otherwise. Ignore non-alphanumeric characters and case.

A palindrome is a string that reads the same forward and backward after removing all non-alphanumeric characters and converting to lowercase.

Example(s)

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Brute Force

JavaScript Solution

/**
 * Check if a string is a palindrome using brute force approach
 * @param {string} s - Input string
 * @return {boolean} - True if palindrome, false otherwise
 */
function isPalindrome(s) {
  // Remove non-alphanumeric characters and convert to lowercase
  const cleanString = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
  
  // Check if the cleaned string equals its reverse
  return cleanString === cleanString.split('').reverse().join('');
}

Python Solution

import re

def is_palindrome(s: str) -> bool:
    """
    Check if a string is a palindrome using brute force approach
    
    Args:
        s: Input string
        
    Returns:
        bool: True if palindrome, false otherwise
    """
    # Remove non-alphanumeric characters and convert to lowercase
    clean_string = re.sub(r'[^a-zA-Z0-9]', '', s).lower()
    
    # Check if the cleaned string equals its reverse
    return clean_string == clean_string[::-1]

Complexity (Brute Force)

• Time Complexity: O(n²) - Due to string reversal operation
• Space Complexity: O(n) - Additional space for cleaned string

Optimized Solution

JavaScript Solution

/**
 * Check if a string is a palindrome using two pointers approach
 * @param {string} s - Input string
 * @return {boolean} - True if palindrome, false otherwise
 */
function isPalindromeOptimized(s) {
  let left = 0;
  let right = s.length - 1;
  
  while (left < right) {
    // Skip non-alphanumeric characters from left
    while (left < right && !/[a-zA-Z0-9]/.test(s[left])) {
      left++;
    }
    
    // Skip non-alphanumeric characters from right
    while (left < right && !/[a-zA-Z0-9]/.test(s[right])) {
      right--;
    }
    
    // Compare characters (case-insensitive)
    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    }
    
    left++;
    right--;
  }
  
  return true;
}

Python Solution

def is_palindrome_optimized(s: str) -> bool:
    """
    Check if a string is a palindrome using two pointers approach
    
    Args:
        s: Input string
        
    Returns:
        bool: True if palindrome, false otherwise
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric characters from left
        while left < right and not s[left].isalnum():
            left += 1
        
        # Skip non-alphanumeric characters from right
        while left < right and not s[right].isalnum():
            right -= 1
        
        # Compare characters (case-insensitive)
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True

Complexity (Optimized)

• Time Complexity: O(n) - Single pass through the string
• Space Complexity: O(1) - Constant extra space

Interactive Code Runner

Test the Brute Force Solution

JavaScript Solution

JavaScript Brute Force Solution

/**
* Check if a string is a palindrome using brute force approach
* @param {string} s - Input string
* @return {boolean} - True if palindrome, false otherwise
*/
function isPalindrome(s) {
// Remove non-alphanumeric characters and convert to lowercase
const cleanString = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();

// Check if the cleaned string equals its reverse
return cleanString === cleanString.split('').reverse().join('');
}

// Test cases
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car")); // false
console.log(isPalindrome(" ")); // true
console.log(isPalindrome("Was it a car or a cat I saw?")); // true

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Brute Force Solution

import re

def is_palindrome(s: str) -> bool:
  """
  Check if a string is a palindrome using brute force approach
  
  Args:
      s: Input string
      
  Returns:
      bool: True if palindrome, false otherwise
  """
  # Remove non-alphanumeric characters and convert to lowercase
  clean_string = re.sub(r'[^a-zA-Z0-9]', '', s).lower()
  
  # Check if the cleaned string equals its reverse
  return clean_string == clean_string[::-1]

# Test cases
print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))  # False
print(is_palindrome(" "))  # True
print(is_palindrome("Was it a car or a cat I saw?"))  # True

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Test the Optimized Solution

JavaScript Solution

JavaScript Optimized Solution

/**
* Check if a string is a palindrome using two pointers approach
* @param {string} s - Input string
* @return {boolean} - True if palindrome, false otherwise
*/
function isPalindromeOptimized(s) {
let left = 0;
let right = s.length - 1;

while (left < right) {
  // Skip non-alphanumeric characters from left
  while (left < right && !/[a-zA-Z0-9]/.test(s[left])) {
    left++;
  }
  
  // Skip non-alphanumeric characters from right
  while (left < right && !/[a-zA-Z0-9]/.test(s[right])) {
    right--;
  }
  
  // Compare characters (case-insensitive)
  if (s[left].toLowerCase() !== s[right].toLowerCase()) {
    return false;
  }
  
  left++;
  right--;
}

return true;
}

// Test cases
console.log(isPalindromeOptimized("A man, a plan, a canal: Panama")); // true
console.log(isPalindromeOptimized("race a car")); // false
console.log(isPalindromeOptimized(" ")); // true
console.log(isPalindromeOptimized("Was it a car or a cat I saw?")); // true

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Optimized Solution

def is_palindrome_optimized(s: str) -> bool:
  """
  Check if a string is a palindrome using two pointers approach
  
  Args:
      s: Input string
      
  Returns:
      bool: True if palindrome, false otherwise
  """
  left, right = 0, len(s) - 1
  
  while left < right:
      # Skip non-alphanumeric characters from left
      while left < right and not s[left].isalnum():
          left += 1
      
      # Skip non-alphanumeric characters from right
      while left < right and not s[right].isalnum():
          right -= 1
      
      # Compare characters (case-insensitive)
      if s[left].lower() != s[right].lower():
          return False
      
      left += 1
      right -= 1
  
  return True

# Test cases
print(is_palindrome_optimized("A man, a plan, a canal: Panama"))  # True
print(is_palindrome_optimized("race a car"))  # False
print(is_palindrome_optimized(" "))  # True
print(is_palindrome_optimized("Was it a car or a cat I saw?"))  # True

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Takeaways

• Two-pointers approach is more efficient than string reversal for palindrome checking
• Character filtering can be done inline during comparison to avoid extra space
• Case-insensitive comparison is essential for this problem
• Edge cases like empty strings and single characters should be handled properly
• Regular expressions provide clean character filtering but may have performance overhead