Valid Palindrome — Two Pointer Skip Non-Alphanumeric [Meta Easy]

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forward and backward.

Input: "A man, a plan, a canal: Panama" → true Input: "race a car" → false

Intuition
C Solution
C++ Solution
Java Solution
JavaScript Solution
Python Solution
Complexity: O(n) time, O(1) space

Intuition

Two pointers from both ends. Skip non-alphanumeric characters. Compare lowercase versions.

left, right = 0, len(s)-1
while left < right:
    skip non-alnum on left
    skip non-alnum on right
    compare lowercase(s[left]) vs lowercase(s[right])
    if different → return False
    advance both
return True

C Solution

#include <stdbool.h>
#include <ctype.h>
#include <string.h>

bool isPalindrome(char* s) {
    int l = 0, r = strlen(s) - 1;
    while (l < r) {
        while (l < r && !isalnum(s[l])) l++;
        while (l < r && !isalnum(s[r])) r--;
        if (tolower(s[l]) != tolower(s[r])) return false;
        l++; r--;
    }
    return true;
}

C++ Solution

#include <string>
#include <cctype>
using namespace std;

class Solution {
public:
    bool isPalindrome(string s) {
        int l = 0, r = (int)s.size() - 1;
        while (l < r) {
            while (l < r && !isalnum(s[l])) l++;
            while (l < r && !isalnum(s[r])) r--;
            if (tolower(s[l++]) != tolower(s[r--])) return false;
        }
        return true;
    }
};

Java Solution

class Solution {
    public boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
            while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
            if (Character.toLowerCase(s.charAt(l++)) !=
                Character.toLowerCase(s.charAt(r--))) return false;
        }
        return true;
    }
}

JavaScript Solution

function isPalindrome(s) {
    const clean = s.toLowerCase().replace(/[^a-z0-9]/g, '');
    let l = 0, r = clean.length - 1;
    while (l < r) {
        if (clean[l++] !== clean[r--]) return false;
    }
    return true;
}

Python Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        filtered = [c.lower() for c in s if c.isalnum()]
        return filtered == filtered[::-1]
        # Two pointer:
        # l, r = 0, len(s)-1
        # while l < r:
        #     while l < r and not s[l].isalnum(): l += 1
        #     while l < r and not s[r].isalnum(): r -= 1
        #     if s[l].lower() != s[r].lower(): return False
        #     l += 1; r -= 1
        # return True

Complexity: O(n) time, O(1) space

Follow-up — Palindrome II: Can you make a string palindrome by removing at most one character? → Try removing s[left] or s[right] when a mismatch is found, check if remainder is palindrome.