Valid Palindrome in Java DSA: Two Pointers from the Outside In

Learn Valid Palindrome in Java DSA step by step. Move from brute force to a clean two-pointer scan with full dry runs, code, and complexity comparisons for interviews.

1. Introduction

Valid Palindrome in Java is where two-pointer thinking gets its first real workout. You have met arrays already in this series. Here you learn to walk a string from both ends at once.

The task sounds simple. You get a string of text. You must decide if it reads the same forwards and backwards.

One twist trips people up. You ignore anything that is not a letter or a number. You also treat capital and small letters as the same.

We build the answer in three steps, same as always. Brute force cleans the string, then reverses it. A cleaner version keeps the clean string but drops the reverse. The final one skips the extra string and walks two pointers inward in place.

Every approach comes with full, step-by-step dry runs on the same inputs. We trace a real palindrome and a non-palindrome, so you see both a true and a false result. Nothing is skipped.

2. Understanding the Problem

Let us pin down the rules before touching code.

• You get a string, like “A man, a plan, a canal: Panama”.
• Ignore every character that is not a letter or a digit.
• Treat capital and small letters as the same.
• After that cleaning, the string must read the same both ways.
• Return true if it is a palindrome, and false if it is not.

For that famous phrase the answer is true. Strip the spaces, commas and colon, lowercase everything, and you get “amanaplanacanalpanama”. That reads the same from either side. An empty string counts as a palindrome too.

3. Concepts You Need Here

3.1 Character Checks and Case

Java gives us two small helpers that do the boring work for us.

• Character.isLetterOrDigit(c) tells you if a character is a letter or a number.
• Character.toLowerCase(c) turns any capital into its small version.

3.2 The Two-Pointer Idea

Keep two pointers walking toward each other. One pointer left starts at the far left. The other pointer right starts at the far right end.

• Characters match? Move both pointers inward.
• Characters differ? It is not a palindrome, stop and return false.
• Pointers meet in the middle? Every pair matched, so return true.

Think of two people reading a shelf from opposite ends. They compare the books they hold, then each steps inward. If every pair matches until they meet, the shelf is a mirror image.

4. Approach 1: Brute Force

Clean the string into a fresh version. Then reverse that clean string and compare the two. It uses extra memory, but it proves you understand the goal.

4.1 Pseudocode

clean = empty string
for each char c in s:              // keep only letters and digits
    if c is a letter or a digit:
        add lowercase(c) to clean
 
reversed = clean written backwards // flip the clean string
 
if clean equals reversed:          // compare the two
    return true
else:
    return false

4.2 Pseudocode Explained

• Walk the string once and copy only letters and digits into clean.
• Lowercase each character as you copy, so case stops mattering.
• Build a second string that is clean written backwards.
• A palindrome equals its own reverse, so compare the two.
• Equal means true; different means false.

4.3 Java Code

public class ValidPalindromeBrute {
 
    public static boolean isPalindrome(String s) {
        StringBuilder clean = new StringBuilder();
 
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                clean.append(Character.toLowerCase(c));
            }
        }
 
        String forward = clean.toString();
        String reversed = clean.reverse().toString();
 
        return forward.equals(reversed);
    }
 
    public static void main(String[] args) {
        String s = "Nurses run";
        System.out.println(isPalindrome(s)); // true
    }
}

4.4 Java Code Explained

• Line 4 makes an empty StringBuilder to collect characters.
• Lines 6 to 10 loop the string and keep only letters and digits, lowercased.
• Line 12 saves the clean string, and line 13 makes its reverse.
• Line 15 returns true only when the two strings match.
• We use StringBuilder because it grows fast and reverses in one call.

4.5 Dry Run of the Brute Force

Input: s = “Nurses run”. The loop checks each character in order and builds clean. We trace all ten characters, so nothing is hidden. Watch clean grow on the right.

After the loop, clean is “nursesrun”. Now the last two lines finish the job.

4.6 Reading the Dry Run

Let us walk the whole trace and see what each step did to clean.

Steps 1 to 6: the first word goes in.

• Step 1 reads N. It is a letter, so we lowercase it to n and append. clean is now “n”.
• Steps 2 to 6 read u, r, s, e, s in turn. All are letters, so they append one by one, giving “nurses”.

Step 7: the space is skipped.

• Step 7 reads the space at index 6. It is not a letter or digit, so nothing happens. clean stays “nurses”.

Steps 8 to 10: the second word goes in.

• Step 8 reads r and appends it, giving “nursesr”.
• Next, step 9 reads u and appends it, giving “nursesru”.
• Finally, step 10 reads n and appends it, giving “nursesrun”.

The final check.

• We reverse “nursesrun” and get “nursesrun”, the same string.
• Since forward equals reversed, the method returns true.

So the filter dropped one space and kept nine letters. The two extra strings, clean and reversed, are the memory cost we cut next.

4.7 Time and Space Cost

• Time is O(n), because each pass visits the characters once.
• Space is O(n), since clean and reversed can grow as large as the input.

Two extra strings is fine for five characters. For a million it doubles the memory, which is why we improve it.

5. Approach 2: Clean Once, Then Compare Ends

We do not really need the reverse string. Once we have the clean string, we can compare its two ends ourselves. Keep the cleaning step, but drop the reverse.

5.1 Pseudocode

clean = empty string
for each char c in s:              // clean the string first
    if c is a letter or a digit:
        add lowercase(c) to clean
 
left = 0
right = clean.length - 1
 
while left < right:                // walk inward from both ends
    if clean[left] != clean[right]:
        return false
    left = left + 1
    right = right - 1
 
return true

5.2 Pseudocode Explained

• Clean the string exactly like the brute force did.
• Put left at the start of clean and right at the end.
• While they have not met, compare the two characters.
• Different characters mean not a palindrome, so return false.
• If they match, step both pointers inward and keep going.

5.3 Java Code

public class ValidPalindromeClean {
 
    public static boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                sb.append(Character.toLowerCase(c));
            }
        }
 
        String clean = sb.toString();
        int left = 0;
        int right = clean.length() - 1;
 
        while (left < right) {
            if (clean.charAt(left) != clean.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
 
    public static void main(String[] args) {
        String s = "Nurses run";
        System.out.println(isPalindrome(s)); // true
    }
}

5.4 Java Code Explained

• Lines 4 to 9 clean the string, exactly as before.
• Lines 12 and 13 set left to the start and right to the last index.
• Line 15 loops while left stays to the left of right.
• Line 16 returns false the moment a pair does not match.
• Lines 19 and 20 step both pointers inward after a match.

5.5 Dry Run of the Clean-and-Compare Approach

Input: s = “Nurses run”. Cleaning gives clean = “nursesrun” (the same ten-step filter as before). Now the pointers compare the ends of “nursesrun”. We trace every pass, nothing skipped.

After step 4, left is 4 and right is 4, both on the middle e. Since left is no longer less than right, the loop ends and the method returns true.

Now try a non-palindrome to see a false result. Input: s = “Race a car”, which cleans to “raceacar”. Watch it fail partway.

The first three pairs match, so “raceacar” looks promising. But at step 4, e does not equal a, so the method returns false right away.

5.6 Reading the Dry Run

Let us walk both traces and see how the pointers decide the answer.

Palindrome case: “nursesrun”.

• Steps 1 to 4 compare the outer pairs n-n, u-u, r-r, and s-s. Every pair matches, so both pointers keep stepping inward.
• After step 4, left and right both land on index 4, the middle e. The check left < right is now false, so the loop stops.
• Every pair matched, so the method returns true.

Non-palindrome case: “raceacar”.

• Steps 1 to 3 compare r-r, a-a, and c-c. These match, so the string still looks like it could be a palindrome.
• Step 4 compares e at index 3 with a at index 4. They differ, so the mirror is broken.
• The method returns false at once, without checking anything else.

Notice the win over brute force. We used only two integer pointers, no reverse string. But we still built the clean string once, which the final approach removes.

5.7 Time and Space Cost

• Time is O(n), one pass to clean and one pass to scan.
• Space is O(n), since the clean string can grow as large as the input.

We dropped the reverse copy, which is real progress. One clean string still costs memory, and the final approach removes even that.

6. Approach 3: Two Pointers with No Extra String

Skip the clean string entirely. Run the two pointers straight on the original text. When a pointer lands on a space or comma, it simply steps over it.

6.1 Pseudocode

left = 0
right = s.length - 1
 
while left < right:
    while left < right and s[left] is not a letter or digit:
        left = left + 1                     // skip junk on the left
    while left < right and s[right] is not a letter or digit:
        right = right - 1                   // skip junk on the right
 
    if lowercase(s[left]) != lowercase(s[right]):
        return false
    left = left + 1
    right = right - 1
 
return true

6.2 Pseudocode Explained

• Start left at the first character and right at the last.
• First inner loop: if left sits on junk, step it forward until it hits a real character.
• Second inner loop: if right sits on junk, step it back until it hits a real character.
• Now both point at real characters, so lowercase them and compare.
• Match means step both inward; a mismatch means return false.

6.3 Java Code

public class ValidPalindromeTwoPointer {
 
    public static 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--;
            }
 
            char a = Character.toLowerCase(s.charAt(left));
            char b = Character.toLowerCase(s.charAt(right));
            if (a != b) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
 
    public static void main(String[] args) {
        String s = "Nurses run";
        System.out.println(isPalindrome(s)); // true
    }
}

6.4 Java Code Explained

• Lines 4 and 5 set left to the start and right to the last index.
• The inner loops on lines 8 to 10 and 11 to 13 skip junk on each side.
• Once both point at real characters, lines 15 and 16 lowercase them.
• Line 17 returns false the moment a pair does not match.
• Lines 20 and 21 step both pointers inward after a match.

6.5 Dry Run of the Two-Pointer Scan

Input: s = “Nurses run”, used raw with no cleaning. The pointers scan the original string and skip the space live. We trace every pass, nothing skipped.

Step 4 is the interesting one. After step 3, right sat on the space at index 6. The inner skip loop pulled it back to index 5 before comparing. After step 4, both pointers meet at index 4, the middle e, so the loop ends and returns true.

Now the non-palindrome. Input: s = “Race a car”, scanned raw. Watch it fail partway.

At step 4, right skips the space at index 6, then compares e with a. They differ, so the method returns false without scanning the rest.

6.6 Reading the Dry Run

Let us walk both scans and see how the skip loops and the compare work together.

Palindrome case: “Nurses run”.

• Steps 1 to 3 compare N-n, u-u, and r-r. No junk sits at the ends, so no skipping happens and every pair matches.
• Step 4 is special. Right had reached the space at index 6, so the skip loop moved it back to 5. Then s and s match, and both pointers step to index 4.
• Now left and right both sit on the middle e. The check left < right is false, so the loop stops and returns true.

Non-palindrome case: “Race a car”.

• Steps 1 to 3 compare R-r, a-a, and c-c, all matching, so the scan keeps going.
• Step 4 skips the space on the right, then compares e with a. They differ, so the mirror breaks.
• The method returns false at once, leaving the rest of the string unscanned.

Notice how the skip happens live, in the middle of the scan, with no separate cleaning pass. That is what keeps the extra memory down to two pointers.

6.7 Comparing the Three Traces

Same idea, same answer, three very different amounts of memory.

On five characters the difference looks small. On a very long string it becomes the difference between two extra copies and almost no extra memory at all.

7. The Dry Run on Paper

Tables are precise, but a sketch often lands faster. Here is the same two-pointer scan drawn by hand.

The string sits along the top with its indices. Each step block on the left shows the two characters we compare. The panel on the right shows what the pointers found.

• A gold box marks the first pair, where K and k match after lowercasing.
• The green box marks the moment the pointers meet in the middle.
• Down at the bottom, the finished answer reads true.

8. Comparing the Three Approaches

All three give a correct answer. They just pay different prices for it.

Notice that all three run in linear time. The real story here is space, not speed. The brute force wastes two strings, while the final scan carries just two integers.

In an interview, start with brute force to show you understand the goal. Then explain the wasted memory you spotted. Finally tighten it into the two-pointer scan.

9. Common Mistakes and Edge Cases

A few small traps catch beginners here. Keep them in mind.

• Forgetting to lowercase is the most common slip. Then A and a wrongly count as different.
• Dropping the skip guard left < right can push a pointer off the end of the string.
• An empty string “” should return true, since there is nothing to break the mirror.
• Punctuation-only input, like “,.”, should also return true after skipping.
• Any single character, like “a”, is always a palindrome by itself.

Run those last three cases through your code before you call it done. They catch more bugs than any ordinary input will.

10. Interview Questions

11. Conclusion

Valid Palindrome in Java looks like a warm-up, and in a way it is. But the two-pointer, in-place pattern inside it is a real skill.

Our traces showed the payoff clearly. Brute force needed two extra strings. The two-pointer scan needed just two integers and a single sweep.

So take the pattern, not just the answer. Reach for a clean copy only when you truly must. The moment you can scan in place, a left pointer and a right pointer often do the whole job.

That habit turns three passes into one here. It will do the same for many string problems waiting further down the list.

12. Further Reading

• LeetCode Valid Palindrome problem — practice the original problem and submit your own solution.
• Oracle Java Character documentation — the official reference for isLetterOrDigit and toLowerCase used here.
• Previous in this series: Merge Sorted Array in Java — merge two sorted arrays in place by filling from the back.
• Next in this series: Reverse String in Java — flip a character array in place using two pointers.

javahandson.com | DSA Series | Arrays & Strings