Valid Palindrome

1. Problem & Core Objective

The problem

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

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

Input:  "A man, a plan, a canal: Panama"    Output: true     ("amanaplanacanalpanama")
Input:  "race a car"                        Output: false    ("raceacar")
Input:  " "                                 Output: true     ("" — empty is a palindrome)

Constraints:

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

What the interviewer is actually testing

The palindrome check itself is three lines. The question is really about handling messy input without allocating.

1. Do you reach for two converging pointers? Palindrome = symmetric comparison, which is the canonical converging-pointer shape.
2. Can you skip junk in place, rather than building a cleaned copy? The naive solution filters into a new string — O(n) space. The optimal one never allocates.
3. Do you guard the inner skip loops? This is the actual bug in the problem. A string of pure punctuation runs a pointer off the end unless you re-check the bound inside the skip loop.
4. Do you know the definition includes digits? "Alphanumeric", not "alphabetic" — "0P" is not a palindrome, and it's a real LeetCode test case.

2. First-Principles Thought Process

Step 1 — Constraints

n up to 2 × 10^5. O(n) is comfortable; O(n²) would be 4 × 10^10 and far too slow. So the answer is a single pass — the only question is whether it costs extra memory.

"Printable ASCII" means the input can contain spaces, punctuation, digits, and mixed case. Everything that isn't a letter or digit must be ignored.

Step 2 — Restate the definition mechanically

"Reads the same forwards and backwards" means:

For every valid position i counting from the left, the character there equals the character at the matching position counting from the right.

That's a statement about pairs of positions mirrored around the centre — which immediately suggests one pointer at each end, walking inward.

Step 3 — The obvious solution

Clean the string first, then check:

1. Filter out non-alphanumerics and lowercase everything → a new string.
2. Compare it against its reverse.

Correct and readable, but it allocates two O(n) strings. For a 200,000-character input that's real memory doing work the algorithm doesn't need.

Step 4 — The reframe

Why build a cleaned copy at all? The only reason is to make the indices line up. But you can get the same effect by skipping junk on the fly:

Keep a left pointer and a right pointer. Before each comparison, advance each past any character that isn't alphanumeric. Then compare, and step both inward.

No copy, no extra memory. The skipping happens as part of the walk.

Step 5 — Find the bug before you write it

The skip loops are while loops that advance a pointer. What if there's nothing to stop them?

Consider s = ".,;". Every character is punctuation. The left pointer advances looking for an alphanumeric... and runs straight off the end of the string, throwing StringIndexOutOfBoundsException.

The fix: re-check l < r inside each skip loop, not just in the outer loop. When the pointers meet, everything between them has been consumed and the string is a palindrome by exhaustion.

This is the detail the question is really testing.

3. Solution Paths

Approach 1 — Clean, then compare with the reverse

public boolean isPalindrome(String s) {
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (Character.isLetterOrDigit(c)) {
            sb.append(Character.toLowerCase(c));
        }
    }
    String cleaned = sb.toString();
    String reversed = sb.reverse().toString();
    return cleaned.equals(reversed);
}

How it works. Build a cleaned, lowercased string, then compare it to its own reverse.

Note the ordering trap: sb.reverse() mutates the builder in place. You must call sb.toString() before reversing, or cleaned and reversed end up identical and the function always returns true.

• Time: O(n).
• Space: O(n) — two strings plus the builder.

Correct, and fine as a first answer. Say it, then improve it.

Counter-questions on this approach

⭐ "You call sb.toString() before sb.reverse(). What happens if you reverse first?"

The function always returns true. reverse() mutates the builder in place and returns the same object — it doesn't produce a new one. So capturing cleaned after reversing would give you the reversed string for both variables, and comparing it with itself always succeeds. It's a silent bug that passes every palindrome test and fails every non-palindrome.

"You've allocated two strings plus a builder. Is that necessary?"

No. The only reason to build a cleaned copy is to make the indices line up so a symmetric comparison works. I can get the same alignment by skipping junk during the walk itself, which costs two integers instead of O(n).

Approach 2 — Clean, then two pointers on the cleaned string

public boolean isPalindrome(String s) {
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (Character.isLetterOrDigit(c)) sb.append(Character.toLowerCase(c));
    }

    int l = 0, r = sb.length() - 1;
    while (l < r) {
        if (sb.charAt(l) != sb.charAt(r)) return false;
        l++; r--;
    }
    return true;
}

Avoids building the reversed copy, and exits early on the first mismatch — "ab...z" fails on the first comparison instead of after cleaning and reversing everything.

• Time: O(n).
• Space: O(n) — still one cleaned copy.

A genuine improvement, but the allocation remains.

Counter-questions on this approach

⭐ "This still builds a cleaned copy. What have you actually gained over the first version?"

An early exit. A string that mismatches on its first character returns immediately, instead of cleaning the whole input and building a full reversed copy first. That's a real improvement — but the O(n) allocation is still there, so it's a half-step rather than the answer.

Approach 3 — Two pointers with in-place skipping (optimal)

public boolean isPalindrome(String s) {
    int l = 0, r = s.length() - 1;

    while (l < r) {
        while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;   // skip junk on the left
        while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;   // skip junk on the right

        if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) {
            return false;
        }
        l++; r--;
    }
    return true;
}

How it works. Both pointers advance past junk, then compare the two valid characters they land on, then step inward. No copy is ever made.

Trace on "A man, a plan" (abbreviated):

(That input isn't a palindrome; the full example is.)

Trace on "aba":

Trace on "a.":

Then l=1, r=-1, outer loop ends → true. ✓ Comparing a character with itself is harmless.

• Time: O(n) — each pointer moves forward at most n times total; they never backtrack.
• Space: O(1) — two integers.

Counter-questions on this approach

⭐ "What happens on a string of pure punctuation, like ".,"?"

With the inner l < r guards, the pointers simply meet, the comparison compares a character with itself, and it correctly returns true — a string with no alphanumeric characters cleans to "", which is a palindrome. Without those guards the left pointer advances looking for an alphanumeric, walks off the end, and charAt throws.

⭐ "Why does each skip loop need its own l < r check? Isn't the outer while enough?"

No. The outer condition is evaluated once per comparison, but the skip loops advance freely between those evaluations — nothing stops them mid-scan. The bound has to be re-checked inside each skip loop, or a pointer can run past the other and off the end of the string.

"Does 'alphanumeric' include digits?"

Yes, and it matters. "0P" cleans to "0p" and is not a palindrome since '0' != 'p'. Filtering with isLetter instead of isLetterOrDigit would drop the 0, compare "p" against itself, and wrongly return true.

"Why lowercase both sides rather than just one?"

Normalizing only one side is a silent bug — it passes every all-lowercase test and fails the moment the input is mixed case.

Why the inner l < r guard is mandatory

Take s = ".,;" — all punctuation.

Without the guard:

while (!Character.isLetterOrDigit(s.charAt(l))) l++;   // ✗

l goes 0 → 1 → 2 → 3 → charAt(3) on a length-3 string → StringIndexOutOfBoundsException.

With the guard: l stops the moment l == r, the comparison compares that character with itself (equal), and the function correctly returns true — a string with no alphanumeric characters cleans to "", which is a palindrome.

Verified: ".," and ".,;" both return true with the guard and throw without it.

Comparison

4. Why the Optimal Wins

Against cleaning first. All three are O(n) time, so this is purely a space argument — and a real one. At n = 2 × 10^5 the cleaning approaches allocate a 200KB char array that exists only to make indices line up. Skipping in place achieves the same alignment with two integers.

Against the reverse-comparison version. Beyond space, it has no early exit: "a...z" (mismatching on the very first character) still cleans the whole string and builds the full reverse before discovering the failure. The two-pointer version returns after one comparison.

The transferable principle:

Filtering to make indices align is usually unnecessary. Skip the unwanted elements as part of the traversal instead.

The same move appears whenever input contains noise — skipping deleted records, ignoring whitespace in a parser, stepping over sentinels.

Why O(n) time is the floor. You must inspect every character: an adversary can place the mismatch anywhere, including the last position checked. So O(n) is optimal, and O(1) space is optimal because two indices suffice.

5. Java Prerequisites

Character classification

Character.isLetterOrDigit(c);      // true for a-z, A-Z, 0-9 (and Unicode letters/digits)
Character.isLetter(c);
Character.isDigit(c);
Character.toLowerCase(c);
Character.toUpperCase(c);

"Alphanumeric" includes digits. Using isLetter instead of isLetterOrDigit fails on "0P" — a well-known LeetCode test case where the answer is false (because '0' != 'p'), but a letters-only filter would skip the 0 entirely, compare "p" against itself, and wrongly return true.

A caution about Unicode: Character.isLetterOrDigit returns true for letters in any script, not just ASCII. Here the constraints say printable ASCII, so it doesn't matter — but if you needed strict ASCII you'd test the ranges manually:

boolean isAlnum = (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');

Case-insensitive comparison

Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))

Normalize both sides. Lowercasing just one is a silent bug that passes on all-lowercase input.

An alternative avoiding two conversions per comparison:

if (Character.toLowerCase(a) != Character.toLowerCase(b)) return false;

…is already minimal. Pre-lowercasing the whole string would reintroduce the O(n) allocation.

StringBuilder.reverse mutates

StringBuilder sb = new StringBuilder("abc");
String original = sb.toString();     // "abc" — capture BEFORE reversing
sb.reverse();                        // sb is now "cba"
String reversed = sb.toString();

reverse() returns the same builder (for chaining), it does not return a new one. Calling sb.toString() after reversing gives you the reversed string for both variables.

charAt vs toCharArray

s.charAt(i);            // O(1), no allocation — right for random access
s.toCharArray();        // O(n) copy — right for a single sequential pass

The two-pointer solution jumps around by index, so charAt is the correct choice.

String immutability

Java strings cannot be modified in place, which is why "clean the string" always means "build a new one". There is no in-place filter for a String.

6. Interview Communication Guide

Clarifying questions

1. "Should I ignore spaces and punctuation, or only compare the raw string?" — the whole shape of the problem.
2. "Is the comparison case-insensitive?"
3. "Do digits count as valid characters?" — "alphanumeric" says yes, and it's the "0P" trap.
4. "Is the input ASCII or could it be Unicode?" — affects whether Character.isLetterOrDigit is the right predicate.
5. "Is an empty string a palindrome?" — conventionally yes; confirm.

The pitch

"A palindrome reads the same in both directions, so I'll compare characters mirrored around the centre — one pointer at each end, walking inward.

The complication is that spaces, punctuation, and case have to be ignored. The straightforward approach is to build a cleaned, lowercased copy first and then compare — O(n) time but O(n) space.

I can avoid the copy by skipping junk as part of the walk: before each comparison, advance the left pointer past any non-alphanumeric, and the right pointer likewise. Then compare and step inward. That's O(n) time and O(1) space.

One detail I want to get right — the skip loops need their own l < r check, not just the outer loop. Otherwise a string of pure punctuation would run a pointer off the end and throw. With the guard, the pointers just meet and we correctly return true, since a string with no alphanumeric characters is empty and therefore a palindrome."

Edge cases to raise proactively

".," and "0P" are the two to volunteer. The first proves you thought about the skip-loop bound; the second proves you read "alphanumeric" rather than assuming "alphabetic".

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

⭐ "What if you can delete at most one character — is it still a palindrome?"

Same two-pointer walk. On the first mismatch, you have exactly two options: skip the left character, or skip the right. Check whether either remaining substring is a palindrome with a simple helper. Still O(n), because the helper runs at most twice and each call is a single linear scan.

"Find the longest palindromic substring."

Different technique — expand around each of the 2n − 1 centres, since palindromes have odd and even forms. O(n²) time, O(1) space. Manacher's algorithm does it in O(n) but isn't worth attempting live. See 19 — Dynamic Programming.

"What about a palindromic linked list?"

You can't walk backwards. Use fast/slow pointers to find the middle, reverse the second half in place, compare the two halves, then restore. O(n) time, O(1) space. See 11 — Linked List.

"What if the string is streamed and you can't index it?"

Two pointers need random access. You'd buffer it, or — if you only need to detect palindromic prefixes — use rolling hashes computed forwards and backwards and compare them.

"Handle full Unicode properly."

Java char is 16 bits, so characters outside the Basic Multilingual Plane (emoji, rare scripts) occupy two chars as a surrogate pair. Indexing by char would split them and compare halves. The correct approach iterates code points via s.codePointAt(i) and advances by Character.charCount(cp). Also note that in some languages case folding isn't 1:1 — German ß uppercases to SS — so toLowerCase on individual characters isn't universally correct.