Given a string s, return true if it reads the same forwards and backwards after lowercasing and removing every non-alphanumeric character, and false otherwise.
An empty string (after cleaning) counts as a palindrome.
Example
Cleaned to "amanaplanacanalpanama", a palindrome.
Constraints
- 1 <= s.length <= 2 * 10^5
- s consists only of printable ASCII characters.
Intuition
The most direct approach normalizes the string — lowercase it and drop every non-alphanumeric character — then reverses that cleaned copy and checks whether the two strings are identical. A palindrome reads the same forwards and backwards, so it equals its own reverse.
function isPalindrome(s) {
// Normalize: lowercase, then keep only letters and digits.
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, "");
// Build the reversed copy and compare the whole strings.
const reversed = [...cleaned].reverse().join("");
return cleaned === reversed; // equal iff it's a palindrome
}This is O(n) time, but the reversed copy is a second O(n) string we never really need. Can we do better on space?
Notice that comparing a string to its reverse just pairs up the first character with the last, the second with the second-to-last, and so on. We can check those pairs directly on the cleaned string with two pointers — one at each end, walking inward — which is exactly the Two pointers converging-ends pattern. The moment a pair disagrees we can stop early and return false.
Cleaning still costs O(n) space here (we keep the cleaned string), but the comparison itself drops to O(1) extra and short-circuits on the first mismatch instead of always building a full reversed copy.
Walking it through:
cleaned: "abca" — a mismatch (returns false)
The outer pair matches, so move both pointers inward.
The next pair disagrees — stop early, this is not a palindrome.
cleaned: "abba" — a palindrome (returns true)
The outer pair matches, so move both pointers inward.
The inner pair matches too; the pointers now cross.
Every pair matched before the pointers met → it's a palindrome.
Optimization
Clean, then two pointers
First normalize: lowercase and drop every non-alphanumeric character with a regex. Then walk two pointers inward from both ends — if any mismatched pair turns up it isn't a palindrome. An empty cleaned string never enters the loop, so it returns true.
O(n) time, O(n) for the cleaned copy.
function isPalindrome(s) {
// Normalize so case and punctuation can't affect the comparison.
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, "");
// Two pointers converging from the ends compare mirror-image positions.
let i = 0;
let j = cleaned.length - 1;
while (i < j) {
// First disagreeing pair means it can't be a palindrome — stop early.
if (cleaned[i] !== cleaned[j]) return false;
i++;
j--;
}
// Pointers met (or the cleaned string was empty) with no mismatch.
return true;
}Complexity analysis
Time complexity: O(n). Here's why:
- Cleaning the string scans every character once to lowercase it and drop non-alphanumerics — O(n).
- The two pointers then start at opposite ends and only move toward each other, touching each cleaned character at most once — O(n).
Both passes are linear and run one after the other, so the overall time is O(n), where n is the length of s.
Space complexity: O(n). Here's why:
- The cleaned, lowercased copy of the string can be as long as the input — O(n).
- The two-pointer scan over it adds only a couple of index variables — O(1).
The cleaned copy dominates, so the extra space is O(n). (Skipping non-alphanumerics in place on the original string instead of copying would bring this down to O(1).)
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| s = "?!#" | true | All non-alphanumeric — cleans to the empty string, which counts as a palindrome. |
| s = "Z" | true | Single character — trivially reads the same both ways. |
| s = "ab" | false | Smallest non-palindrome: two distinct letters, 'a' != 'b'. |
| s = "AaA" | true | Mixed case that lowercases to 'aaa' — all-equal, so a palindrome. |
| s = "Madam, I'm Adam" | true | Mixed case and punctuation cleaned away leaves 'madamimadam'. |
| s = "1a2" | false | Alphanumeric mix where the ends '1' and '2' differ. |
Try it yourself
Write your solution against the real judge before checking the reference.