Valid Palindrome

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.

Approach: Two Pointers

A brute force approach would be to create a new, filtered string (by stripping out punctuation and spaces and converting to lowercase), and then comparing it to its reverse. However, creating new strings and reversing them takes extra $O(n)$ memory and unnecessary linear passes.

We can optimize this to $O(1)$ space using the Two Pointers technique.

We place one pointer at the beginning of the string (left) and one at the end (right). We move them towards the center, skipping any characters that aren’t letters or numbers. When both pointers are resting on valid alphanumeric characters, we compare them (ignoring case). If they match, we continue moving inward. If they don’t, we immediately return false.

1. Initialize left = 0 and right = s.length - 1.
2. Start a while loop that runs as long as left < right.
3. If the character at left is not alphanumeric, increment left to skip it.
4. Otherwise, if the character at right is not alphanumeric, decrement right to skip it.
5. If both characters are alphanumeric, compare their lowercase versions:
   • If they are not equal, return false.
   • If they are equal, increment left and decrement right to check the next pair.
6. If the loop completes and the pointers cross without any mismatches, return true.

Solution

/**
 * @param {string} s
 * @return {boolean}
 */
function isPalindrome(s) {
    let left = 0;
    let right = s.length - 1;
    
    // Helper function to check if a character is alphanumeric using Regex
    const isAlphanumeric = (char) => /^[a-z0-9]+$/i.test(char);
    
    while (left < right) {
        if (!isAlphanumeric(s[left])) {
            left++;
        } else if (!isAlphanumeric(s[right])) {
            right--;
        } else {
            if (s[left].toLowerCase() !== s[right].toLowerCase()) {
                return false;
            }
            left++;
            right--;
        }
    }
    
    return true;
};

Note: We use a Regular Expression (/^[a-z0-9]+$/i) here because it is highly readable and standard in production codebases. If absolute maximum performance is required in a strict algorithm setting, comparing raw character codes (charCodeAt) is technically faster.

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the length of the string. Both pointers only traverse the string once, moving towards the center, meaning we look at each character at most once.
• Space Complexity: $O(1)$ auxiliary space. We are only maintaining two integer pointers (left and right), so the memory footprint is strictly constant regardless of the string size.