Valid Palindrome

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

EasyTime O(n) · Space O(1)

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 visualizer

See the two pointers move step by step.

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

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

Key insights

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

Solution

TypeScript
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);
}

Time & space complexity

Time complexity

O(n)

Single pass through the string

Space complexity

O(1)

Only two pointers are used

Related problems

Longest Palindromic Substring

Coming soon

Find the longest palindrome within a string.

Valid Palindrome II

Coming soon

Check for a palindrome when at most one character may be deleted.

Palindrome Linked List

Coming soon

Check if a linked list is a palindrome.

Discussion

Questions, ideas or a different approach? Join the conversation.