Valid Palindrome Algorithm

A palindrome reads the same forwards and backwards. But real-world strings have uppercase letters, spaces, punctuation. The actual check is: after stripping non-alphanumeric characters and lowercasing, does it read the same both ways?

Input: "A man, a plan, a canal: Panama"
Output: true ("amanaplanacanalpanama" is a palindrome)

The intuition

Clean the string first. Then use two pointers — one at the start, one at the end. Walk them toward each other, comparing characters. If any pair doesn't match, it's not a palindrome.

var isPalindrome = function(s) {
    s = s.toLowerCase().replace(/[^a-z0-9]/g, '');

    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        if (s[left] !== s[right]) return false;
        left++;
        right--;
    }

    return true;
};

Complexity

• Time: O(n) — the regex pass is O(n), the two-pointer pass is O(n/2).
• Space: O(n) — the cleaned string is a new allocation.

Can you avoid the extra string?

Yes. Skip non-alphanumeric characters inline instead of pre-cleaning:

var isPalindromeNoAlloc = function(s) {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        while (left < right && !/[a-z0-9]/.test(s[left].toLowerCase())) left++;
        while (left < right && !/[a-z0-9]/.test(s[right].toLowerCase())) right--;

        if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
        left++;
        right--;
    }

    return true;
};

Time: O(n). Space: O(1).

The trade-off: the second version avoids allocating a new string but is harder to read. For most use cases, the cleaner first version is the right call. Optimize for readability until profiling proves you need to optimize for memory.