Valid Palindrome

Easy

Check if a string is a palindrome after removing non-alphanumeric characters and ignoring case.

Problem Statement

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. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

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.

Interactive Visualization

String Characters
0
A
1
␣
2
m
3
a
4
n
5
,
6
␣
7
a
8
␣
9
p
10
l
11
a
12
n
13
,
14
␣
15
a
16
␣
17
c
18
a
19
n
20
a
21
l
22
:
23
␣
24
P
25
a
26
n
27
a
28
m
29
a
Pointers
Left Pointer
0
Right Pointer
29
Step 1 / 0Infinity%

Approach: Two Pointers

Algorithm:

  1. Initialize two pointers: left at the start and right at the end
  2. While left < right:
    • Skip non-alphanumeric characters on both sides
    • Compare characters (case-insensitive)
    • If different, return false
    • Move pointers inward
  3. If all characters match, return true

Complexity Analysis:

  • Time Complexity: O(n) - single pass through the string
  • Space Complexity: O(1) - only using two pointers

Key Insights:

  • Two pointers technique efficiently checks from both ends simultaneously
  • In-place comparison without creating a new string saves memory
  • Case-insensitive comparison using toLowerCase() or character code comparison
  • Regular expressions can filter alphanumeric, but two pointers is more efficient

Solution Code

TypeScript/JavaScript:

function isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;
    
    while (left < right) {
        // Skip non-alphanumeric from left
        while (left < right && !isAlphanumeric(s[left])) {
            left++;
        }
        
        // Skip non-alphanumeric from right
        while (left < right && !isAlphanumeric(s[right])) {
            right--;
        }
        
        // Compare characters (case-insensitive)
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }
        
        left++;
        right--;
    }
    
    return true;
}

function isAlphanumeric(char: string): boolean {
    return /[a-zA-Z0-9]/.test(char);
}

Python:

def isPalindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric from left
        while left < right and not s[left].isalnum():
            left += 1
        
        # Skip non-alphanumeric 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

Related Problems

  • Valid Palindrome II - Given at most one character deletion
  • Longest Palindromic Substring - Find the longest palindrome
  • Palindrome Linked List - Check if a linked list is a palindrome

Discussion

Have questions or want to discuss alternative approaches? Join the conversation below.

Back to Strings