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

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

1. Introduction

Valid Palindrome in Java is the seventh problem in this series. It follows Merge Sorted Array, and it opens a brand new topic: the two-pointer scan. 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. But there is a twist that trips up beginners.

You ignore anything that is not a letter or a number. You also ignore the difference between capital and small letters. So a messy phrase with spaces and commas can still be a clean palindrome underneath.

We build the answer in three steps. Brute force cleans the string first, then reverses it. A cleaner version keeps the reverse but drops one loop. The final two-pointer scan skips the extra string entirely and checks in place.

Every approach here comes with a full dry run. We trace the same input through each one, so you can watch the extra memory melt away step by step.

2. Understanding the Problem

Let us fix the rules before we write any code. A clear problem statement now saves you from silent bugs later.

• You get a string, for example “A man, a plan, a canal: Panama”.
• Every character that is not a letter or a digit gets ignored.
• Capital and small letters count as the same thing.
• 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 the colon, lowercase everything, and you get “amanaplanacanalpanama”. That reads the same from either side.

Notice one easy trap. An empty string counts as a palindrome. There is nothing to break the symmetry, so the answer is true.

2.1 Why the Cleaning Rule Matters

The raw string is full of noise. Only the letters and digits carry meaning here.

• Spaces, commas, and colons are decoration. We skip them completely.
• The letter A and the letter a must count as equal. So we lowercase both.
• Only after this cleaning do we compare characters from the two ends.

Miss this rule and a real palindrome looks broken. The comparison would trip over a comma and wrongly answer false.

2.2 Why This Example String

Our phrase is picked to be a little awkward. That keeps the traces honest.

• It mixes capitals and small letters, so case handling gets tested.
• It hides spaces, commas, and a colon among the letters.
• Underneath all that noise it is still a perfect palindrome.

A tidy word like “level” hides all of this. A messy phrase shows you what the cleaning and the pointers really do.

3. Concepts You Need Here

Two small ideas carry this whole problem. Both come back often in later string questions, so learn them well.

3.1 Character Checks and Case

Java gives us small helpers for single characters. They 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.
• Together they let us clean and compare one character at a time.

So we never build a big set of rules by hand. These two helpers cover every case we need.

3.2 The Two-Pointer Idea

Here is the idea that makes this problem click. You keep two pointers walking toward each other.

One pointer starts on the far left. It reads the first character and then steps to the right. We call it left.

The other pointer starts on the far right. It reads the last character and then steps to the left. We call it right.

• The left pointer moves forward, from the start toward the middle.
• The right pointer moves backward, from the end toward the middle.
• They meet in the centre, and that is when the scan is done.

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

4. Approach 1: Brute Force

The first idea most people reach for feels natural. Clean the string into a fresh version first. Then reverse that clean string and compare the two.

It is simple, but it uses extra memory. We build two new strings along the way. Still, it is a good warm-up, and it proves you understand the goal.

4.1 Pseudocode

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

4.2 Reading the Pseudocode

Let us read this slowly, one block at a time. The plan has three clear passes. First we clean, then we reverse, then we compare. Think of it as copying a note onto fresh paper, holding it up to a mirror, and checking the two match.

Start at the very top. We create an empty string called clean. Right now it holds nothing. It will slowly collect only the characters we care about.

Now look at the first loop. It walks the original string from left to right, one character at a time. At each character, it asks one yes-or-no question.

• The question is simple: is this character a letter or a digit?
• When yes, we lowercase it and add it to the back of clean.
• When no, we skip it and move straight to the next character.

So this loop is a filter. Letters and digits pass through, and everything else falls away. Because we read left to right and never reorder, the good characters land in clean in their original sequence. That point matters, since order is the whole idea of a palindrome.

After that loop, pause and picture the state. For our phrase, clean now holds “amanaplanacanalpanama”. Every space, comma, and colon is gone, and every capital is now small. The messy input has become one tidy lowercase string.

Next comes the reverse step. We build a second string that is clean written backwards. If clean is “abcba”, then reversed is also “abcba”. If clean were “abcd”, then reversed would be “dcba”.

Here is the key insight behind the whole approach. A palindrome is a string that equals its own reverse. That is the exact definition we are leaning on.

• If clean and reversed hold the same characters in the same order, the string is a mirror of itself.
• So when clean equals reversed, we can safely return true.
• When they differ at even one spot, the mirror is broken, so we return false.

That final comparison is the whole decision. We do not check character by character ourselves. We let the equals check compare the two strings for us and hand back the answer.

So the whole plan reads as three simple moves: filter the string down to clean characters, flip that clean string, then ask whether the two versions are identical.

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 = "A man, a plan, a canal: Panama";
        System.out.println(isPalindrome(s)); // true
    }
}

4.4 Reading the Java Code

Each part here has one clear job. Let us walk through them slowly.

• Line 4 creates an empty StringBuilder called clean, ready to collect characters.
• The loop on line 6 visits every character in the input string.
• Inside it, line 7 keeps a character only when it is a letter or a digit.
• Then line 8 lowercases that character and appends it to clean.
• After the loop, line 12 saves the tidy forward version as a plain string.
• Right after, line 13 reverses the builder and saves that as reversed.
• Finally, line 15 returns true only when the two strings are equal.

One detail deserves a second look. We use StringBuilder, not a plain String, to collect characters.

• A plain String cannot change once made, so adding to it in a loop is slow.
• A StringBuilder is built to grow, so appending in a loop stays fast.
• It also gives us a handy reverse method, which saves us writing one.

This code is easy to read and hard to get wrong. That is its real strength. The weakness is the extra strings, and we trim them next.

4.5 Dry Run of the Brute Force

Let us trace s = “A man, a plan, a canal: Panama”. Watch clean grow as we filter the first few characters.

The filter keeps going for the rest of the phrase. Once every character has been checked, clean holds the full tidy string.

4.6 Reading the Dry Run

The filter did the heavy lifting, then one compare gave the answer. Let us break that down.

• Steps 2, 6 and 7 met a space or comma, so nothing was added to clean.
• Real characters showed up in steps 1, 3, 4, 5 and 8, so they joined clean in order.
• That capital A in step 1 was lowercased to a before it went in.

Now look at the hidden cost. We built two whole new strings to reach the answer.

• The clean string is as long as the count of letters and digits.
• The reversed string is a second copy of that same length.
• For a short phrase that is fine, but long inputs pay for two extra copies.

4.7 Time and Space Cost

Brute force walks the string a few times, but never nests loops. So the time stays linear.

• 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.

Our phrase needed two extra strings. Grow the input to a million characters and you pay for two million extra slots. That memory cost is the pain point we solve next.

5. Approach 2: Clean Once, Then Compare Ends

The dry run above handed us a hint. We do not really need the reverse string. Once we have the clean string, we can compare its two ends ourselves.

So let us keep the cleaning step, but drop the reverse. We put one pointer at the start of clean and one at the end. Then we walk them inward, comparing as we go.

This version still builds one clean string, so space is not perfect yet. But it removes the second copy and shows the pointer idea in a gentle way.

5.1 Pseudocode

clean = empty string
for each char c in s:              // still 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 Reading the Pseudocode

The first block is the same cleaning step as before, so we will not repeat it. The new idea starts once clean is ready. Instead of reversing, we set up two pointers and let them do the checking.

Look at the two lines that set up the pointers. We put left at index 0, the very first character. We put right at the last index, which is the length minus one.

Now the while loop drives everything. It keeps running as long as left is still to the left of right. The moment they meet or cross, the loop stops.

Inside the loop we make one comparison. We check whether the character at left is different from the character at right.

• If the two characters differ, the string cannot be a palindrome, so we return false at once.
• If they match, we say nothing and simply keep going.
• After a match, we push left one step right and pull right one step left.

Here is why the two pointers move toward each other. A palindrome must mirror around its centre. So the first character should match the last, the second should match the second to last, and so on.

Let us picture it on a small clean string, say “amana”. At the start, left points at the first a and right points at the last a. They match, so left becomes 1 and right becomes 3. Now both point at m and n… wait, they point at m and n only if the string is not a palindrome. In “amana” they point at m and a, which do not match, so this shows how a mismatch would surface. For a true palindrome every such pair lines up.

One more thing about the exit. If the loop finishes without ever returning false, every pair matched. That means the string mirrored perfectly, so we return true at the end.

So the plan is two clean stages: build the tidy string once, then close two pointers inward until they meet, failing fast on any mismatch.

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 = "A man, a plan, a canal: Panama";
        System.out.println(isPalindrome(s)); // true
    }
}

5.4 Reading the Java Code

The shape is simple, so let us focus on why each piece exists.

• Lines 4 to 9 clean the string, exactly as the brute force did.
• Line 12 sets left to 0, the first character of the clean string.
• Line 13 sets right to the last index, the length minus one.
• The while loop on line 15 runs while left stays to the left of right.
• Line 16 fails fast and returns false on any mismatched pair.
• Lines 19 and 20 step the pointers inward after a match.

Compare this with the brute force. The reverse string is gone completely, replaced by two small integers.

• Brute force asked, does the whole clean string equal its full reverse?
• This version flips it and asks, does each outer pair of characters match?
• That pairwise question needs only left and right, not a second string.

5.5 Dry Run of the Clean-and-Compare Approach

Take the small clean string “amana” to keep the trace short. Watch the pointers close inward.

Legend: left is the pointer moving from the start, right is the pointer moving from the end.

That short string “amana” is not a real palindrome, so it fails at step 2. For our true phrase “amanaplanacanalpanama”, every pair would match and the loop would end with true.

5.6 Reading the Dry Run

Two steps settled this small case. Let us look closely.

• Step 1 compared the outer a and a, which matched, so both pointers moved.
• Step 2 compared m and n, which differ, so the method returned false.
• The scan stopped early, without checking the middle of the string.

Notice the memory win over brute force. We used only two integer pointers here.

• The reverse string never appeared, saving one full copy of the input.
• We still built the clean string once, so space is not yet the best.
• That last clean string is exactly what the final approach removes.

6. Approach 3: Two Pointers with No Extra String

The version above is close, but it still builds a clean string. So what is left to improve?

We can skip the clean string entirely. We run the two pointers straight on the original text. When a pointer lands on a space or comma, it simply steps over it.

Think of it as walking the raw string from both ends, ignoring the noise as you pass it. You compare only the real characters, right where they sit.

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 Reading the Pseudocode

This is the tightest version, so let us take it gently. There is no cleaning pass and no extra string. We work on the raw input the whole time. The trick is a pair of small inner loops that skip the junk.

As before, left starts at index 0 and right starts at the last index. The big outer while loop keeps them moving toward each other until they meet.

Now look at the first inner loop. It says: while left is not yet past right, and the character at left is junk, step left forward.

• So if left is sitting on a space, the inner loop nudges it forward.
• It keeps nudging until left lands on a real letter or digit.
• The check left < right stops it from ever running off the end.

The second inner loop does the mirror job on the right side. While right sits on junk, it pulls right backward one step at a time. It stops the moment right lands on a real character.

After both inner loops finish, both pointers sit on real characters. Only now do we compare them. We lowercase each one first, so a capital and a small letter count as equal.

• If the two real characters differ, the mirror is broken, so we return false.
• If they match, we step left forward and right backward, then loop again.

Here is the part beginners find clever. We never copy the string. The skipping happens live, inside the same scan that does the comparing. One walk does both jobs at once.

Let us walk a tiny piece on “a,a”. At the start left is on the first a and right is on the last a. Neither is junk, so no skipping happens. They match, so left moves to index 1 and right moves to index 1. Now left equals right, so the outer loop stops and we return true. The comma in the middle was simply never visited.

One last worry: could a pointer skip too far and cross over? No. Every inner loop carries the guard left < right. The moment the pointers meet, all skipping stops, so they never trade places.

So the plan is a single sweep: skip junk on the left, skip junk on the right, compare the two real characters, then step inward and repeat.

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 = "A man, a plan, a canal: Panama";
        System.out.println(isPalindrome(s)); // true
    }
}

6.4 Reading the Java Code Line by Line

This version does the most thinking in the fewest lines, so let us go gently.

• Line 4 sets left to 0, and line 5 sets right to the last index.
• The outer loop on line 7 runs while the pointers have not met.
• Inside it, lines 8 to 10 skip junk on the left, moving left forward.
• Next, lines 11 to 13 skip junk on the right, moving right backward.
• Once both land on real characters, lines 15 and 16 lowercase them before comparing.
• Line 17 returns false the moment a pair fails to match.
• Finally, lines 20 and 21 step both pointers inward after a match.

Two details separate this from the clean-and-compare version.

• There is no clean string, because the skipping happens live in the scan.
• We lowercase each character on the spot, so no lowercased copy is stored.

Because each character is visited at most once, one sweep is enough. That single idea is what makes this solution shine.

6.5 Dry Run of the Two-Pointer Scan

Now we trace a short raw string “a,a” one final time. Watch the comma get skipped only when a pointer reaches it.

Legend: left scans from the start, right scans from the end, and junk is skipped live.

6.6 Reading the Dry Run

Two steps end the whole thing. Let us look at each one closely.

• Step 1 compared the outer a and a, which matched, so both pointers moved inward.
• Step 2 found left and right both at index 1, so the outer loop stopped.
• The comma at index 1 was never compared, because the loop had already ended.

This case never needed the skip loops, since the ends were both real letters. A messier string shows the skipping in action.

• On “A man…”, the skip loops step over spaces and commas as pointers reach them.
• Each real character is still visited exactly once during the whole scan.
• So the work stays linear, even with lots of punctuation to skip.

6.7 Comparing the Three Traces

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

The gap grows with size. On a short phrase 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 and the question we ask. The panel on the right shows what the pointers found.

Follow the colour cues as you read it.

• 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.

Some people read pictures faster than tables. Use whichever version clicks for you, or sketch your own on paper while you follow the code.

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.

That climb from wasteful to lean is exactly the story interviewers want to hear. Jumping straight to the optimal answer skips the reasoning they came to observe.

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.
• Forgetting 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.
• A string of only punctuation, like “,.”, should also return true after skipping.
• A single character, like “a”, is always a palindrome by itself.

Run those last three cases through your code before you say you are finished. They catch more bugs than any normal 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 of the same size. 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 turned 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.
• 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: https://javahandson.com/reverse-string-in-java/