Loading…

easyStringsLC #125Frequently asked

Valid Palindrome

Q: How do you solve Valid Palindrome using the Brute Force — Clean Then Compare With Reverse approach?

When to use it: Say it first — it's the most readable translation of the definition and a fine baseline before optimizing space. Translate the definition directly: walk the string once, keep only characters where `isalnum()` is true, and lowercase each as you go into a fresh buffer. Then test whether that buffer equals its reverse. **Why this is the natural first attempt.** The problem statement *is* an algorithm: 'convert uppercase to lowercase, remove non-alphanumeric, then check it reads the same both ways.' Building the cleaned string mirrors those words one-to-one, so it's almost impossible to get the logic wrong — which is exactly why it's a good baseline to state out loud. **Why it's still O(n) and correct.** Filtering is a single linear scan, and comparing a string to its reverse is another linear scan. Both are O(n), so the time is optimal. The only blemish is the O(n) buffer. **Why we don't ship this.** With `n` up to `2 × 10⁵` the extra string is harmless in practice, but the interviewer is probing whether you can avoid the allocation entirely. Allocating a second copy when two indices would do is the thing to improve — so mention this, then pivot to two pointers. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Valid Palindrome using the Two Pointers — In-Place Skip (Optimal) approach?

When to use it: The answer they want. Phrase it as 'walk inward from both ends, skipping anything that isn't alphanumeric'. Keep two indices: `l` at the start and `r` at the end. Repeatedly advance `l` past non-alphanumeric characters and retreat `r` past them, then compare the two alphanumeric characters case-insensitively. If they ever differ, it's not a palindrome; otherwise step both inward and continue until the pointers meet. **The mental shift that unlocks this.** The brute force allocates a cleaned string just so it can compare position `i` with position `n−1−i`. But those positions already exist in the original string — we only need a way to *skip the junk between them*. Two pointers do exactly that without ever materializing a second buffer. **Why the inner skip loops need the `l < r` guard.** Imagine a string that is all punctuation, like ",.;". The left pointer keeps advancing looking for an alphanumeric character and would run off the end of the string. Guarding each inner `while` with `l < r` stops the skip the instant the pointers meet, so we never index out of bounds and an all-symbol string correctly returns true. **Why lowercasing both sides matters.** The comparison is case-insensitive, so 'A' at the left must match 'a' at the right. Lowercasing (or uppercasing) both characters right before the comparison handles that uniformly — forgetting it makes "Aa" report as a non-palindrome. **Why this is O(1) space.** We never build a new string. The only state is two integer indices, regardless of input size. That's the entire reason to prefer this over clean-and-compare. Time complexity: O(n). Space complexity: O(1).

LCPractice

Two Pointers · 1 of 30 · 7 min

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters 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. Alphanumeric characters include letters and numbers.

In plain English

Strip out punctuation, spaces, and symbols; treat upper and lower case as equal; then ask whether the remaining letters-and-digits sequence is a mirror of itself. We don't build the cleaned string if we don't have to — two pointers can skip the junk on the fly.

Examples

Example 1

Input: s = "A man, a plan, a canal: Panama"
Output: true
Note: After filtering and lowercasing it becomes "amanaplanacanalpanama", which is a palindrome.

Example 2

Input: s = "race a car"
Output: false
Note: Filtered to "raceacar", which is not a palindrome (first 'r' vs last 'r' ok, but 'a' vs 'a'… 'c' vs 'c'… eventually 'e' vs 'a' mismatch).

Example 3

Input: s = " "
Output: true
Note: Only a space, which is non-alphanumeric. The filtered string is empty, and an empty string is a palindrome.

Constraints

1 ≤ s.length ≤ 2 × 10⁵
s consists only of printable ASCII characters

Clarifying questions4First question: Do digits count, or only letters?Explore questions

Q1.Do digits count, or only letters?
Digits count. 'Alphanumeric' = letters and numbers, so "0P" is not a palindrome but "121" is.
Q2.Is the comparison case-sensitive?
No — convert to a single case first. 'A' and 'a' must be treated as equal.
Q3.What about an empty string or one with only symbols?
After filtering it becomes empty, and an empty string reads the same both ways → return true.
Q4.Can I allocate a new cleaned string?
You can, and it's simplest, but it costs O(n) space. In-place two pointers gets the same answer in O(1) extra space.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Ignore everything that isn't a letter or digit, compare case-insensitively, and check the string reads the same forwards and backwards. The interview-grade answer is two pointers from both ends that skip non-alphanumeric characters in place — O(n) time, O(1) space. The 'clean a new string then reverse' version is fine to mention but uses O(n) extra space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can filter characters in place with two pointers instead of allocating a cleaned copy, and whether you remember digits count as alphanumeric and the compare is case-insensitive.

Where candidates slip

Only skipping letters (forgetting digits), comparing without lowercasing, or dropping the `l < r` guard inside the skip loops so the pointers run off the ends.

How to stand out

State the O(n)-space clean-and-compare version, then improve to in-place two pointers for O(1) space. Call out that 'alphanumeric' includes digits and that the comparison is case-insensitive.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Clean Then Compare With Reverse	`O(n)`	`O(n)`	Say it first — it's the most readable translation of the definition and a fine baseline before optimizing space.	Read
2	Two Pointers — In-Place Skip (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'walk inward from both ends, skipping anything that isn't alphanumeric'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewIs the string a palindrome (alnum only)?Is O(1) extra space required?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Clean Then Compare With Reverse

TimeO(n)SpaceO(n)

Say it first — it's the most readable translation of the definition and a fine baseline before optimizing space.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The definition literally tells you the transformation: drop non-alphanumeric characters and lowercase the rest. What's the simplest data structure to hold the result?

2Hint 2Explore hint

Build a new string (or list) of just the lowercased alphanumeric characters.

3Hint 3Explore hint

A string is a palindrome iff it equals its own reverse. Compare the cleaned string to its reverse and return the boolean.

A · Core idea

Translate the definition directly: walk the string once, keep only characters where isalnum() is true, and lowercase each as you go into a fresh buffer. Then test whether that buffer equals its reverse.

Why this is the natural first attempt. The problem statement is an algorithm: 'convert uppercase to lowercase, remove non-alphanumeric, then check it reads the same both ways.' Building the cleaned string mirrors those words one-to-one, so it's almost impossible to get the logic wrong — which is exactly why it's a good baseline to state out loud.

Why it's still O(n) and correct. Filtering is a single linear scan, and comparing a string to its reverse is another linear scan. Both are O(n), so the time is optimal. The only blemish is the O(n) buffer.

Why we don't ship this. With n up to 2 × 10⁵ the extra string is harmless in practice, but the interviewer is probing whether you can avoid the allocation entirely. Allocating a second copy when two indices would do is the thing to improve — so mention this, then pivot to two pointers.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "A man, a plan"

filter

keep letters, lowercase them

Statecleaned = "amanaplan"

Final resultfalse

C · Code with teaching comments

Reference implementation previewpublic boolean isPalindrome(String s) { StringBuilder sb = new StringBuilder(); for (char c : s.toCharArray()) { if (Character.isLetterOrDigit(c)) { sb.append(Character.toLowerCase(c));Explore the full code

solution.javaJava

Brute Force — Clean Then Compare With Reverse — reference

3 teaching notes

1
public boolean isPalindrome(String s) {
2
    StringBuilder sb = new StringBuilder();
3
    for (char c : s.toCharArray()) {
4
        // Keep letters AND digits — 'alphanumeric' is not just letters.
5
        if (Character.isLetterOrDigit(c)) {
6
            // Normalize case while building so the later compare is case-insensitive.
7
            sb.append(Character.toLowerCase(c));
8
        }
9
    }
10
    String cleaned = sb.toString();
11
    String reversed = sb.reverse().toString();
12
    // A string is a palindrome iff it equals its own reverse.
13
    return cleaned.equals(reversed);
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Reversing-and-comparing is the most literal encoding of 'reads the same backwards'. It's correct and O(n) time — the only thing wrong with it is the O(n) space, which is precisely the door the interviewer wants you to open toward two pointers.

ComplexityO(n) time, O(n) space — One pass to filter (O(n)) plus one pass to compare with the reverse (O(n)) = O(n) time. The cleaned copy holds up to n characters → O(n) space.

E · Edge cases and pitfalls3Filtering only letters (Character.isLetter) and dropping digits — '0P' would wrongly pass.Explore edge cases

Pitfalls

Filtering only letters (Character.isLetter) and dropping digits — '0P' would wrongly pass.
Forgetting to lowercase, so 'Aa' is reported as not a palindrome.
Allocating the cleaned copy when the interviewer asked for O(1) space.

03.2

Approach 2 of 2 · Optimal

Two Pointers — In-Place Skip (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'walk inward from both ends, skipping anything that isn't alphanumeric'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't actually need the cleaned string — you only need to compare matching positions. What if you tracked a left and a right index into the original string?

2Hint 2Explore hint

Move a left pointer rightward and a right pointer leftward. Before comparing, skip over any non-alphanumeric character on either side.

3Hint 3Explore hint

At each step, lowercase and compare s[l] with s[r]. If they differ, return false. Otherwise step both inward. Stop when l meets or passes r.

A · Core idea

Keep two indices: l at the start and r at the end. Repeatedly advance l past non-alphanumeric characters and retreat r past them, then compare the two alphanumeric characters case-insensitively. If they ever differ, it's not a palindrome; otherwise step both inward and continue until the pointers meet.

The mental shift that unlocks this. The brute force allocates a cleaned string just so it can compare position i with position n−1−i. But those positions already exist in the original string — we only need a way to skip the junk between them. Two pointers do exactly that without ever materializing a second buffer.

Why the inner skip loops need the `l < r` guard. Imagine a string that is all punctuation, like ",.;". The left pointer keeps advancing looking for an alphanumeric character and would run off the end of the string. Guarding each inner while with l < r stops the skip the instant the pointers meet, so we never index out of bounds and an all-symbol string correctly returns true.

Why lowercasing both sides matters. The comparison is case-insensitive, so 'A' at the left must match 'a' at the right. Lowercasing (or uppercasing) both characters right before the comparison handles that uniformly — forgetting it makes "Aa" report as a non-palindrome.

Why this is O(1) space. We never build a new string. The only state is two integer indices, regardless of input size. That's the entire reason to prefer this over clean-and-compare.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "a,b a"

Array state

l=0, r=4

'a' vs 'a' — match, step inward

l ↓

[0]

[1]

[2]

[3]

r ↓

[4]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

solution.javaJava

Two Pointers — In-Place Skip (Optimal) — optimal

4 teaching notes

1
public boolean isPalindrome(String s) {
2
    int l = 0, r = s.length() - 1;
3
    while (l < r) {
4
        // Skip left-side junk; the l < r guard stops us running off the end on
5
        // all-symbol input.
6
        while (l < r && !Character.isLetterOrDigit(s.charAt(l))) {
7
            l++;
8
        }
9
        // Symmetric skip from the right.
10
        while (l < r && !Character.isLetterOrDigit(s.charAt(r))) {
11
            r--;
12
        }
13
        // Case-insensitive compare of the two meaningful characters.
14
        if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) {
15
            return false;
16
        }
17
        l++;
18
        r--;
19
    }
20
    return true;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Two pointers turn 'compare the string to its reverse' into 'compare the i-th and (n−1−i)-th meaningful characters as we go' — same comparison, no buffer. The in-place skip is the reusable trick: whenever you'd build a filtered copy only to scan it, ask whether two indices into the original can do the job.

ComplexityO(n) time, O(1) space — Each pointer moves monotonically toward the other and never backtracks, so every index is visited at most once → O(n) time. Only two integer indices are stored → O(1) extra space.

E · Edge cases and pitfalls6s = " " — Single space is non-alnum; both skip loops collapse l and r to the same spot, loop never compares → return true.Explore edge cases

Edge cases handled

s = " "Single space is non-alnum; both skip loops collapse l and r to the same spot, loop never compares → return true.
s = "0P"'0' vs 'P' lowercased to '0' vs 'p' — mismatch → return false. Confirms digits participate.
s = ".,"All non-alphanumeric; left skip moves l to r immediately → return true.

Pitfalls

Dropping the inner `l < r` guard — pointers run off the ends on all-symbol strings and crash.
Comparing without lowercasing — 'Aa' wrongly fails.
Using `isLetter` instead of `isLetterOrDigit` — silently treats digits as junk.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean isPalindrome(String s) { int l = 0, r = s.length() - 1; while (l < r) { while (l < r && !Character.isLetterOrDigit(s.charAt(l))) { l++;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping only letters, not digits

'Alphanumeric' includes 0-9. Filtering with isLetter drops digits, so "121" loses its digits and the logic breaks.

Explore the code comparison

Don't write this

if (Character.isLetter(c)) {
    sb.append(Character.toLowerCase(c));
}

Write this instead

if (Character.isLetterOrDigit(c)) {
    sb.append(Character.toLowerCase(c));
}

Missing the l < r guard in the skip loop

On an all-symbol string the skip loop keeps advancing and indexes past the end of the string, throwing an exception.

Explore the code comparison

Don't write this

while not s[l].isalnum():
    l += 1   # runs off the end if no alnum chars remain

Write this instead

while l < r and not s[l].isalnum():
    l += 1

Forgetting case-insensitivity

Comparing raw characters makes 'A' != 'a', so palindromes with mixed case are wrongly rejected.

Explore the code comparison

Don't write this

if s[l] != s[r]:
    return False

Write this instead

if s[l].lower() != s[r].lower():
    return False

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two pointers from both ends, skip non-alphanumeric

Code pattern to memorize

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

Rules to remember

1Compare alphanumeric only — letters AND digits, not just letters.
2Lowercase (or uppercase) both characters before comparing — 'A' must equal 'a'.
3Guard every inner skip loop with l < r so pointers never cross past each other.
4Two pointers in place is O(1) space; building a cleaned string is O(n) — say which one you're doing and why.
5An empty string (or one with no alphanumeric chars) is a valid palindrome → return true.

Use this pattern when

Check symmetry / mirror property of a sequence
Compare characters from both ends inward with a filter
Any 'reads the same backwards' question on strings or arrays
You want O(1) extra space instead of cleaning into a new buffer

Choose another pattern when

Need to find the longest palindromic substring → expand-around-center / DP, not a single scan
Allowed to remove at most k characters → DP or greedy two-pointer with a branch
Linked list palindrome → reverse second half with fast/slow pointers

Interview takeaway

Opposite-end two pointers with an in-place skip is the canonical O(1)-space palindrome check. The same skeleton powers Valid Palindrome II, Reverse String, and the merge step of Two Sum II — recognise it whenever you compare a sequence against its mirror.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternOpposite-end two pointers with an in-place filter. Reach for it whenever you compare a sequence against its mirror and want O(1) space. Same skeleton as Reverse String, Valid Palindrome II, and the merge of Two Sum II.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Palindrome II
Allowed to delete at most one character — on a mismatch, branch and check both skip-left and skip-right substrings.
Palindrome Number
Coming soon
Same idea on an integer — reverse half the digits without converting to a string.
Palindrome Linked List
Coming soon
Find the middle with fast/slow, reverse the second half, then compare both halves.
Longest Palindromic Substring
Coming soon
Expand around each center — the two-pointer idea, but growing outward instead of shrinking inward.

Same pattern

Continue · Next problem

3Sum

easyStringsLC #125Frequently asked

Valid Palindrome

LCPractice

Two Pointers · 1 of 30 · 7 min

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters 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. Alphanumeric characters include letters and numbers.

In plain English

Examples

Example 1

Input: s = "A man, a plan, a canal: Panama"
Output: true
Note: After filtering and lowercasing it becomes "amanaplanacanalpanama", which is a palindrome.

Example 2

Input: s = "race a car"
Output: false
Note: Filtered to "raceacar", which is not a palindrome (first 'r' vs last 'r' ok, but 'a' vs 'a'… 'c' vs 'c'… eventually 'e' vs 'a' mismatch).

Example 3

Input: s = " "
Output: true
Note: Only a space, which is non-alphanumeric. The filtered string is empty, and an empty string is a palindrome.

Constraints

1 ≤ s.length ≤ 2 × 10⁵
s consists only of printable ASCII characters

Clarifying questions4First question: Do digits count, or only letters?Explore questions

Q1.Do digits count, or only letters?
Digits count. 'Alphanumeric' = letters and numbers, so "0P" is not a palindrome but "121" is.
Q2.Is the comparison case-sensitive?
No — convert to a single case first. 'A' and 'a' must be treated as equal.
Q3.What about an empty string or one with only symbols?
After filtering it becomes empty, and an empty string reads the same both ways → return true.
Q4.Can I allocate a new cleaned string?
You can, and it's simplest, but it costs O(n) space. In-place two pointers gets the same answer in O(1) extra space.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can filter characters in place with two pointers instead of allocating a cleaned copy, and whether you remember digits count as alphanumeric and the compare is case-insensitive.

Where candidates slip

Only skipping letters (forgetting digits), comparing without lowercasing, or dropping the `l < r` guard inside the skip loops so the pointers run off the ends.

How to stand out

State the O(n)-space clean-and-compare version, then improve to in-place two pointers for O(1) space. Call out that 'alphanumeric' includes digits and that the comparison is case-insensitive.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Clean Then Compare With Reverse	`O(n)`	`O(n)`	Say it first — it's the most readable translation of the definition and a fine baseline before optimizing space.	Read
2	Two Pointers — In-Place Skip (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'walk inward from both ends, skipping anything that isn't alphanumeric'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Clean Then Compare With Reverse

TimeO(n)SpaceO(n)

Say it first — it's the most readable translation of the definition and a fine baseline before optimizing space.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The definition literally tells you the transformation: drop non-alphanumeric characters and lowercase the rest. What's the simplest data structure to hold the result?

2Hint 2Explore hint

Build a new string (or list) of just the lowercased alphanumeric characters.

3Hint 3Explore hint

A string is a palindrome iff it equals its own reverse. Compare the cleaned string to its reverse and return the boolean.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "A man, a plan"

filter

keep letters, lowercase them

Statecleaned = "amanaplan"

Final resultfalse

C · Code with teaching comments

solution.javaJava

Brute Force — Clean Then Compare With Reverse — reference

3 teaching notes

1
public boolean isPalindrome(String s) {
2
    StringBuilder sb = new StringBuilder();
3
    for (char c : s.toCharArray()) {
4
        // Keep letters AND digits — 'alphanumeric' is not just letters.
5
        if (Character.isLetterOrDigit(c)) {
6
            // Normalize case while building so the later compare is case-insensitive.
7
            sb.append(Character.toLowerCase(c));
8
        }
9
    }
10
    String cleaned = sb.toString();
11
    String reversed = sb.reverse().toString();
12
    // A string is a palindrome iff it equals its own reverse.
13
    return cleaned.equals(reversed);
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — One pass to filter (O(n)) plus one pass to compare with the reverse (O(n)) = O(n) time. The cleaned copy holds up to n characters → O(n) space.

E · Edge cases and pitfalls3Filtering only letters (Character.isLetter) and dropping digits — '0P' would wrongly pass.Explore edge cases

Pitfalls

Filtering only letters (Character.isLetter) and dropping digits — '0P' would wrongly pass.
Forgetting to lowercase, so 'Aa' is reported as not a palindrome.
Allocating the cleaned copy when the interviewer asked for O(1) space.

03.2

Approach 2 of 2 · Optimal

Two Pointers — In-Place Skip (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'walk inward from both ends, skipping anything that isn't alphanumeric'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't actually need the cleaned string — you only need to compare matching positions. What if you tracked a left and a right index into the original string?

2Hint 2Explore hint

Move a left pointer rightward and a right pointer leftward. Before comparing, skip over any non-alphanumeric character on either side.

3Hint 3Explore hint

At each step, lowercase and compare s[l] with s[r]. If they differ, return false. Otherwise step both inward. Stop when l meets or passes r.

A · Core idea

Why this is O(1) space. We never build a new string. The only state is two integer indices, regardless of input size. That's the entire reason to prefer this over clean-and-compare.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "a,b a"

Array state

l=0, r=4

'a' vs 'a' — match, step inward

l ↓

[0]

[1]

[2]

[3]

r ↓

[4]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

solution.javaJava

Two Pointers — In-Place Skip (Optimal) — optimal

4 teaching notes

1
public boolean isPalindrome(String s) {
2
    int l = 0, r = s.length() - 1;
3
    while (l < r) {
4
        // Skip left-side junk; the l < r guard stops us running off the end on
5
        // all-symbol input.
6
        while (l < r && !Character.isLetterOrDigit(s.charAt(l))) {
7
            l++;
8
        }
9
        // Symmetric skip from the right.
10
        while (l < r && !Character.isLetterOrDigit(s.charAt(r))) {
11
            r--;
12
        }
13
        // Case-insensitive compare of the two meaningful characters.
14
        if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) {
15
            return false;
16
        }
17
        l++;
18
        r--;
19
    }
20
    return true;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6s = " " — Single space is non-alnum; both skip loops collapse l and r to the same spot, loop never compares → return true.Explore edge cases

Edge cases handled

s = " "Single space is non-alnum; both skip loops collapse l and r to the same spot, loop never compares → return true.
s = "0P"'0' vs 'P' lowercased to '0' vs 'p' — mismatch → return false. Confirms digits participate.
s = ".,"All non-alphanumeric; left skip moves l to r immediately → return true.

Pitfalls

Dropping the inner `l < r` guard — pointers run off the ends on all-symbol strings and crash.
Comparing without lowercasing — 'Aa' wrongly fails.
Using `isLetter` instead of `isLetterOrDigit` — silently treats digits as junk.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean isPalindrome(String s) { int l = 0, r = s.length() - 1; while (l < r) { while (l < r && !Character.isLetterOrDigit(s.charAt(l))) { l++;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping only letters, not digits

'Alphanumeric' includes 0-9. Filtering with isLetter drops digits, so "121" loses its digits and the logic breaks.

Explore the code comparison

Don't write this

if (Character.isLetter(c)) {
    sb.append(Character.toLowerCase(c));
}

Write this instead

if (Character.isLetterOrDigit(c)) {
    sb.append(Character.toLowerCase(c));
}

Missing the l < r guard in the skip loop

On an all-symbol string the skip loop keeps advancing and indexes past the end of the string, throwing an exception.

Explore the code comparison

Don't write this

while not s[l].isalnum():
    l += 1   # runs off the end if no alnum chars remain

Write this instead

while l < r and not s[l].isalnum():
    l += 1

Forgetting case-insensitivity

Comparing raw characters makes 'A' != 'a', so palindromes with mixed case are wrongly rejected.

Explore the code comparison

Don't write this

if s[l] != s[r]:
    return False

Write this instead

if s[l].lower() != s[r].lower():
    return False

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two pointers from both ends, skip non-alphanumeric

Code pattern to memorize

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

Rules to remember

1Compare alphanumeric only — letters AND digits, not just letters.
2Lowercase (or uppercase) both characters before comparing — 'A' must equal 'a'.
3Guard every inner skip loop with l < r so pointers never cross past each other.
4Two pointers in place is O(1) space; building a cleaned string is O(n) — say which one you're doing and why.
5An empty string (or one with no alphanumeric chars) is a valid palindrome → return true.

Use this pattern when

Check symmetry / mirror property of a sequence
Compare characters from both ends inward with a filter
Any 'reads the same backwards' question on strings or arrays
You want O(1) extra space instead of cleaning into a new buffer

Choose another pattern when

Need to find the longest palindromic substring → expand-around-center / DP, not a single scan
Allowed to remove at most k characters → DP or greedy two-pointer with a branch
Linked list palindrome → reverse second half with fast/slow pointers

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Palindrome II
Allowed to delete at most one character — on a mismatch, branch and check both skip-left and skip-right substrings.
Palindrome Number
Coming soon
Same idea on an integer — reverse half the digits without converting to a string.
Palindrome Linked List
Coming soon
Find the middle with fast/slow, reverse the second half, then compare both halves.
Longest Palindromic Substring
Coming soon
Expand around each center — the two-pointer idea, but growing outward instead of shrinking inward.

Same pattern

Continue · Next problem

3Sum