Valid Palindrome

EasyalgorithmsTwo pointers

Maintained by Vikas Dulgunde, software engineer

You are given a string that may contain letters, digits, spaces, and punctuation. The goal is to test whether it is a palindrome, but only the alphanumeric characters count. Every space, comma, colon, underscore, or other symbol is ignored entirely.

Comparison is case insensitive, so an uppercase 'A' and a lowercase 'a' are considered the same character. After filtering and lowercasing, the remaining sequence must be identical when read left to right and right to left.

Return true when that filtered sequence is a palindrome and false otherwise. A string with no alphanumeric characters at all (including an empty string) counts as a palindrome because there is nothing that breaks the symmetry.

Examples

Input: "A man, a plan, a canal: Panama"

Output: true

Stripping non-alphanumerics and lowercasing gives 'amanaplanacanalpanama', which reads the same in both directions.

Input: "race a car"

Output: false

The cleaned form is 'raceacar'. The first character 'r' does not match the last character 'r' once you fold inward: 'raceacar' reversed is 'racaecar', so it is not a palindrome.

Input: " "

Output: true

A single space has no alphanumeric characters, so the filtered string is empty and is treated as a palindrome.

Input: "ab_a"

Output: true

The underscore is skipped, leaving 'aba', which is symmetric.

Constraints

The input is a string that can be empty.
Characters may include printable ASCII letters, digits, spaces, and punctuation.
Only the characters [0-9a-zA-Z] are compared; everything else is ignored.
Letter comparison ignores case.

Visible test cases

isPalindrome("A man, a plan, a canal: Panama") == true
isPalindrome("race a car") == false
isPalindrome(" ") == true
isPalindrome("ab_a") == true

Hints

Hint 1

First picture the simplest version: build a new string of just the lowercased letters and digits, then check it against its reverse.

Hint 2

You do not actually need a second copy of the string. Two indices, one at each end, can walk toward the middle and compare as they go.

Hint 3

When a pointer lands on a non-alphanumeric character, advance that pointer without comparing. Only compare when both pointers sit on alphanumeric characters.

Loading the editor...

Approaches

Filter then compare with reverse

Time O(n) · Space O(n)

Reduce the messy input to a clean canonical form, then a palindrome check is trivial.

Walk through the string and keep only characters that are letters or digits, lowercasing each one.
Join those kept characters into a new string.
Compare that string to its reverse and return whether they are equal.

Two pointers in place

Time O(n) · Space O(1)

Compare from both ends inward while skipping characters that do not count, so no extra string is built.

Set a left pointer at index 0 and a right pointer at the last index.
While left is less than right, advance left past any non-alphanumeric character and move right back past any non-alphanumeric character.
Compare the lowercased characters at left and right; if they differ, return false.
Step both pointers one place inward and continue until they meet or cross, then return true.

Common mistakes

Forgetting that an empty or all-punctuation string must return true rather than false.
Treating the underscore as alphanumeric. In many built-in word-character checks '_' counts as a word character, but here only [0-9a-zA-Z] qualify, so 'ab_a' must skip the underscore.
Comparing characters without lowercasing, which wrongly rejects inputs like 'Aa'.
Letting a skip loop run past the other pointer; guard each inner skip with the left-less-than-right condition so the pointers cannot cross.

Follow-up variations

What changes if you must also allow the string to be a palindrome after deleting at most one character?
How would you handle full Unicode, where case folding and 'what counts as alphanumeric' are far more involved than ASCII?
Could you stream the check over a very large input that does not fit in memory, comparing from both ends without loading it all at once?

Build the rest of your prep

All coding problems

Practice problems by company

The NeetCode 150 roadmap

Guide: coding interview patterns

Examples

Input: "A man, a plan, a canal: Panama"

Output: true

Stripping non-alphanumerics and lowercasing gives 'amanaplanacanalpanama', which reads the same in both directions.

Input: "race a car"

Output: false

The cleaned form is 'raceacar'. The first character 'r' does not match the last character 'r' once you fold inward: 'raceacar' reversed is 'racaecar', so it is not a palindrome.

Input: " "

Output: true

A single space has no alphanumeric characters, so the filtered string is empty and is treated as a palindrome.

Input: "ab_a"

Output: true

The underscore is skipped, leaving 'aba', which is symmetric.

Hints

Hint 1

First picture the simplest version: build a new string of just the lowercased letters and digits, then check it against its reverse.

Hint 2

You do not actually need a second copy of the string. Two indices, one at each end, can walk toward the middle and compare as they go.

Hint 3

When a pointer lands on a non-alphanumeric character, advance that pointer without comparing. Only compare when both pointers sit on alphanumeric characters.

Approaches

Filter then compare with reverse

Time O(n) · Space O(n)

Reduce the messy input to a clean canonical form, then a palindrome check is trivial.

Walk through the string and keep only characters that are letters or digits, lowercasing each one.
Join those kept characters into a new string.
Compare that string to its reverse and return whether they are equal.

Two pointers in place

Time O(n) · Space O(1)

Compare from both ends inward while skipping characters that do not count, so no extra string is built.

Set a left pointer at index 0 and a right pointer at the last index.
While left is less than right, advance left past any non-alphanumeric character and move right back past any non-alphanumeric character.
Compare the lowercased characters at left and right; if they differ, return false.
Step both pointers one place inward and continue until they meet or cross, then return true.

Common mistakes

Forgetting that an empty or all-punctuation string must return true rather than false.

Treating the underscore as alphanumeric. In many built-in word-character checks '_' counts as a word character, but here only [0-9a-zA-Z] qualify, so 'ab_a' must skip the underscore.

Comparing characters without lowercasing, which wrongly rejects inputs like 'Aa'.

Letting a skip loop run past the other pointer; guard each inner skip with the left-less-than-right condition so the pointers cannot cross.

Follow-up variations

What changes if you must also allow the string to be a palindrome after deleting at most one character?

How would you handle full Unicode, where case folding and 'what counts as alphanumeric' are far more involved than ASCII?

Could you stream the check over a very large input that does not fit in memory, comparing from both ends without loading it all at once?

Valid Palindrome

Examples

Constraints

Hints

Approaches

Filter then compare with reverse

Two pointers in place

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep

Valid Palindrome

Examples

Constraints

Hints

Approaches

Filter then compare with reverse

Two pointers in place

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep