A content desk flags headlines that still read the same after punctuation is gone and case is folded. Marketing wants the badge; the CMS has to say yes or no. The first version built a cleaned StringBuilder, reversed a copy, and compared. A day’s titles returned instantly. A backfill of the archive allocated a second string for every row and the worker’s heap climbed until the pod restarted.

Valid Palindrome asks whether a phrase matches from both ends once you ignore non-alphanumeric characters and fold case. s.charAt(i) is already free. Filter-then-reverse uses that and still pays an extra O(n) copy.

This is an interview writeup, not a two-pointers lecture. The two pointers post owns the left/right walk. Here we only care about skipping junk so the remaining pair is a real comparison.

The problem

Given a String s, return true if the letters and digits in s form a palindrome. Ignore every other character. Treat 'A' and 'a' as the same. After that filter, an empty result is a palindrome.

s = "A man, a plan, a canal: Panama"  →  true
s = "race a car"                      →  false
s = " "                               →  true    nothing left to disagree

Note: This is a filtered phrase, not a contiguous slice. Longest palindromic substring asks for a window inside the original string. Different prompt; do not recycle this skip-and-compare proof.

Filter and reverse is the honest brute force

Keep lowercase alphanumerics, reverse a copy, compare. Correct. Extra linear space.

boolean isPalindromeCleaned(String s) {
    StringBuilder cleaned = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isLetterOrDigit(c)) {
            cleaned.append(Character.toLowerCase(c));
        }
    }
    StringBuilder reversed = new StringBuilder(cleaned).reverse();
    return cleaned.toString().equals(reversed.toString());
}

At a tweet this is a rounding error. At a backfill of archive titles you paid a second string for a question two pointers answer in place: do the real characters still match from the ends?

Two pointers from the ends

Start lo at 0 and hi at n - 1. Skip non-alphanumeric characters on whichever side is sitting on punctuation. Compare Character.toLowerCase of the two remaining characters. Mismatch: false. Match: step both inward. When the pointers meet, nothing disagreed.

Walk the Panama headline from the ends, then the false case:

s = "A man, a plan, a canal: Panama"

lo=0  'A'   hi=29 'a'    both alnum, lower equal, inward
lo=1  ' '   skip lo
lo=2  'm'   hi=28 'm'    equal
lo=3  'a'   hi=27 'a'
lo=4  'n'   hi=26 'n'
lo=5  ','   skip lo
...
pointers cross, return true

s = "race a car"

lo=0 'r'   hi=9 'r'     equal
lo=1 'a'   hi=8 'a'
lo=2 'c'   hi=7 'c'
lo=3 'e'   hi=6 ' '     skip hi
lo=3 'e'   hi=5 'a'     'e' != 'a', return false

The Java is that walk:

boolean isPalindrome(String s) {
    int lo = 0;
    int hi = s.length() - 1;
    while (lo < hi) {
        while (lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) {
            lo++;
        }
        while (lo < hi && !Character.isLetterOrDigit(s.charAt(hi))) {
            hi--;
        }
        if (lo >= hi) {
            break;
        }
        if (Character.toLowerCase(s.charAt(lo)) != Character.toLowerCase(s.charAt(hi))) {
            return false;
        }
        lo++;
        hi--;
    }
    return true;
}

Time is O(n) — each index is visited at most once. Space is O(1) besides the two indexes.

Note: Skip only while lo < hi, then break if they crossed. If the inner loops omit the bound, lo can walk off the end on all-punctuation input and charAt throws. If you compare after the skips without lo >= hi, ".," compares two junk characters and returns false. Crossing without a leftover pair is the empty-after-filter case: return true.

What interviewers usually poke next

  • Whitespace / punctuation only. " " and ".," filter to empty. Return true. Say that before they ask you to special-case length.
  • ASCII vs Unicode. Character.isLetterOrDigit accepts letters outside A-Z. If they want [0-9A-Za-z] only, say the range test out loud and write it.
  • Allow one deletion. That is a different prompt. This walk has no skip-a-mismatch branch; do not pretend it does.
  • Null. Production would reject. At the board, ask.

You are done with this problem when you can say, out loud, why the cleaned reverse is correct, why two pointers skip instead of allocating, and why empty-after-filter is true.