Valid Palindrome [Easy] — Two Pointers Inward

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

Two pointers from both ends. Skip non-alphanumeric characters, then compare. If any mismatch, return false.

Solutions

C

#include <ctype.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;
    }
    return true;
}

C++

bool isPalindrome(string s) {
    int l=0, r=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

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

var isPalindrome = function(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

def isPalindrome(s: str) -> bool:
    filtered = [c.lower() for c in s if c.isalnum()]
    return filtered == filtered[::-1]

# Two-pointer O(1) space:
def isPalindrome_ptr(s: str) -> bool:
    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

Time: O(n)
Space: O(1) with two-pointer approach

Follow-ups

Valid Palindrome II (allow deleting one character)
Palindrome Pairs (Word Ladder variant)