You are given a string s.
Your task is to determine whether it is a valid palindrome after:

Ignoring all non-alphanumeric characters
Converting all letters to lowercase

A palindrome reads the same forwards and backwards.

---

Understanding the Problem

We only care about:

A–Z, a–z
0–9

All other characters (spaces, commas, punctuation, etc.) must be skipped.

Examples:

Input: “A man, a plan, a canal: Panama”
Output: true
Explanation: After filtering → “amanaplanacanalpanama”

Input: “race a car”
Output: false

Input: ” ” (only spaces)
Output: true (empty string is a palindrome)

---

Approach (Explained in Simple Language)

The most efficient way is to use the two-pointer technique.

Step 1: Set two pointers

left = 0
right = s.length() – 1

Step 2: Move pointers inward

Skip characters that are NOT letters or digits.

Use Character.isLetterOrDigit(c)

Step 3: Compare characters

Convert both characters to lowercase
If they are not equal → return false

Else move both pointers inward.

Step 4: If pointers cross

Return true.

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

This is the optimal solution.

---

Java Code

public class ValidPalindrome {

    public boolean isPalindrome(String s) {

        int left = 0;
        int right = s.length() - 1;

        while (left < right) {

            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }

            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }

            if (Character.toLowerCase(s.charAt(left)) != 
                Character.toLowerCase(s.charAt(right))) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }

    public static void main(String[] args) {
        ValidPalindrome sol = new ValidPalindrome();
        System.out.println(sol.isPalindrome("A man, a plan, a canal: Panama"));
    }
}

---

Dry Run

Input:
“A man, a plan, a canal: Panama”

Let’s process step by step.

Left pointer at index 0: ‘A’
Right pointer at index 29: ‘a’

Both are alphanumeric.

Compare lowercase:

‘a’ == ‘a’ → OK
Move inward.

---

Left → ‘ ‘ (space) → skip
Left → ‘m’
Right → ‘m’

Match → move inward.

---

Left → ‘a’
Right → ‘a’

Match → move inward.

---

Left → ‘n’
Right → ‘n’

Match → move inward.

---

Continue this pattern…

Eventually all pairs match.

Pointers cross → return true.

---

Another dry run:

Input:
“race a car”

String after filtering would be “raceacar”

Check:

r == r
a == a
c == c
e != a → mismatch

Return false.

---

Why This Approach Works

Two-pointer technique allows us to:

Avoid allocating extra strings
Skip non-alphanumeric characters efficiently
Compare only meaningful characters
Do everything in a single pass

It guarantees O(n) performance and minimal memory usage.