Valid Palindrome easy

Description

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

Given a string s, return true if it is a palindrome, or false otherwise.

Examples

> Case 1:
    s = "A man, a plan, a canal: Panama"
    Output: true
    Explanation: filtered = "amanaplanacanalpanama" — a palindrome.
 
> Case 2:
    s = "race a car"
    Output: false
    Explanation: filtered = "raceacar" — not a palindrome.
 
> Case 3:
    s = " "
    Output: true
    Explanation: filtered = "" — an empty string is trivially a palindrome.

Constraints

• 1 <= s.length <= 2 × 10^5
• s consists only of printable ASCII characters.

State design

1. Flavor? Opposite-ends.
2. Pointers? l = 0, r = n − 1.
3. Movement? Skip non-alphanumerics on each side. Once both point at alphanumerics, compare lowercased characters. If equal, advance both. If not, return false.
4. Stop? When l >= r. If we never returned false, return true.

Code

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;
        l++; r--;
    }
    return true;
}

def is_palindrome(s):
    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

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;
        l++; r--;
    }
    return true;
}

Why not just build a filtered string and compare?

def is_palindrome_brute(s):
    filtered = "".join(c.lower() for c in s if c.isalnum())
    return filtered == filtered[::-1]

That works! It’s O(n) time. The catch: O(n) extra space for the filtered string and its reverse. The two-pointer version is O(1) extra. For an interview, the in-place version demonstrates the pattern; for production, either is fine.

Analysis

• Time: O(n). Each character is touched by l at most once and by r at most once.
• Space: O(1).

Same skin

• Valid Palindrome II — allowed to delete at most one character; on first mismatch, try skipping l or r and check if the rest is a palindrome.
• Palindrome Linked List — find middle, reverse second half, compare with first.
• Longest Palindromic Substring — expand from center (two pointers from each potential center).
• Reverse Vowels of a String — opposite-ends, swap only at vowels.