Valid Palindrome Problem in DSA: Two Pointers Explained Simply

Learn Valid Palindrome problem in DSA with a clean two pointer solution. Includes beginner friendly code, a full dry run, and O(1) space explained step by step.

1. Introduction

The Valid Palindrome problem in DSA is the question that finally makes the two pointer idea click for most beginners. It sounds easy at first glance. Yet the tricky part hides in the details, and those details are exactly what interviewers poke at.

Here is the task in plain words. You get a string. Spaces, commas, colons and every other symbol get ignored. Capital letters and small letters count as the same thing. After that cleanup, you answer one question: does the text read the same forward and backward?

Take the classic example, “A man, a plan, a canal: Panama”. Strip the punctuation and lowercase everything, and you get amanaplanacanalpanama. Read that backward and you land on the same letters. So the answer is true.

In this guide we start with the obvious reverse-the-string approach. Then we move to the two pointer version that interviewers want. We dry run the code by hand, so you can watch each pointer move step by step.

2. Understanding the Problem

Let us pin down the rules first. Most bugs in this problem come from a rule someone skipped, not from bad logic.

• You get a string that can hold letters, digits, spaces and punctuation.
• Only letters and digits matter. Everything else gets ignored.
• Case does not matter, so a capital P and a small p count as equal.
• Return true when the cleaned text reads the same in both directions.
• An empty string counts as a palindrome, so the answer there is true.

That last rule surprises people. After you strip symbols from a string like “.,”, nothing is left. An empty text reads the same in both directions, so it passes.

Notice that digits count too. The string “1a2” is not a palindrome, but “1a1” is. Many beginners filter letters only and quietly break this case.

3. Concepts You Need Here

Two small ideas carry this whole problem. Both come back in many string questions later, so it pays to learn them properly.

3.1 Cleaning Characters

Every language gives you two small checks that do the heavy lifting here. The first asks whether a character is a letter or a digit. The second converts a character to lowercase.

Together these two checks let you skip junk and compare fairly. You never have to write your own alphabet list, and you never have to worry about where the capital letters sit in the character table.

Think about why lowercasing matters. Computers store each character as a number, and a capital P carries a different number from a small p. Comparing them directly would report a mismatch even though a reader sees the same letter. Flattening case first removes that trap.

3.2 The Two Pointer Walk

Picture two fingers on the string. One finger starts at the far left. The other starts at the far right. Both walk toward the middle, one step at a time.

At every stop, you compare the two characters under your fingers. Matching characters mean you keep going. A mismatch means the string fails right there, so you stop early.

When the fingers meet or cross, you have checked every pair. Nothing is left to compare, so the string passes.

4. Approach 1: Clean and Reverse

The first idea most people reach for is direct. Build a clean version of the string, reverse it, then check whether both versions match.

4.1 Pseudocode

clean = empty text
for each character c in s:
    if c is a letter or a digit:
        add lowercase c to clean
 
reversed = reverse of clean
return clean equals reversed

4.2 Java Implementation

public class ValidPalindromeReverse {
 
    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 backward = clean.reverse().toString();
 
        return forward.equals(backward);
    }
 
    public static void main(String[] args) {
        String s = "A man, a plan, a canal: Panama";
        System.out.println(isPalindrome(s)); // true
    }
}

4.3 Why This Works, Step by Step

Let us walk the logic slowly. The method does its work in three clear stages, and each stage has one job.

Stage one is collection. We create an empty text buffer that will hold only the characters we care about. A plain string would work too, but adding to a string repeatedly rebuilds it every single time. A buffer grows in place instead, which keeps the cost low.

Stage two is filtering. The loop visits every character in the original text exactly once. For each one, we ask a single question: is this a letter or a digit? Spaces, commas and colons all answer no, so they never reach the buffer. Anything that answers yes gets lowercased and appended.

Stage three is comparison. We take the collected text, produce its reverse, then check whether the two versions hold the same characters in the same order.

Here is the subtle part that trips people up. Reversing a buffer usually flips it in place rather than handing back a fresh copy. So the original buffer is now the reversed one. If you read your forward text out of that same buffer afterwards, you read the reversed version twice and the comparison always succeeds.

The fix is ordering. Save the forward text into its own variable before you reverse anything. Once you store the forward copy safely, flipping the buffer cannot damage it. That single line of discipline is the difference between a correct solution and one that returns true for every input you throw at it.

Notice what the comparison at the end actually does. It checks the characters, not the memory location. Two separate pieces of text holding the same letters count as equal, which is exactly what we want here.

4.4 Time and Space Cost

The loop touches each character once, so cleaning takes O(n) time. Reversing and comparing also cost O(n). Added together, the time stays O(n).

Space is the weak spot. We build a second copy of the text, so memory grows to O(n). For most inputs that is fine. Interviewers still push you to remove it.

5. Approach 2: The Two Pointer Solution

Now for the version interviewers really want. The trick is simple: never build a copy at all. Instead, compare the string against itself from both ends.

One pointer starts at index zero. Another starts at the last index. Both skip anything that is not a letter or a digit. Whenever both land on real characters, you compare them.

5.1 Pseudocode

left = 0
right = last index of s
 
while left < right:
    skip left forward while s[left] is not a letter or digit
    skip right backward while s[right] is not a letter or digit
 
    if lowercase s[left] != lowercase s[right]:
        return false
 
    move left one step right
    move right one step left
 
return true

5.2 Java Implementation

public class ValidPalindromeTwoPointers {
 
    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
    }
}

5.3 Reading the Code Line by Line

This version does more thinking, so let us break it apart piece by piece.

Setup comes first. One pointer named left starts at position zero, the very first character. Another pointer named right starts at the last position, which is the length minus one. That minus one matters. Counting starts at zero, so the final character always sits one place below the length.

The outer loop runs while left sits strictly before right. Reading that condition carefully tells you when the work is finished. Once the pointers meet or cross, they have already covered every pair, so nothing remains to do.

Inside the loop, two skip loops run before any comparison happens. The first pushes left forward as long as it points at something that is not a letter or a digit. The second pulls right backward under the same rule. After both finish, each pointer rests on a real character without fail.

Look closely at those two skip loops, because they repeat the left before right check inside their own conditions. That repetition is not clumsy copy-paste. It is the guard that stops a pointer from running off the end of the text.

Picture a string built only from punctuation. The left pointer keeps skipping forward, finds no letter anywhere, and without the guard it would march straight past the final position. Reading a character there crashes the program. With the guard, left simply stops the moment it reaches right, the outer loop ends, and the method reports true.

Comparison comes next. We lowercase both characters before checking them, so a capital letter at one end still matches a small letter at the other. Only after that flattening do we test whether the two characters differ.

A mismatch ends everything immediately. One bad pair is enough to prove the text is not a palindrome, so there is no reason to inspect the remaining characters. Returning early like this is what keeps the method fast on inputs that fail near the outside edges.

When the characters match, both pointers step one place toward the middle. Left moves up, right moves down, and the untested region shrinks from both sides at once.

Finally, reaching the end of the loop means no pair ever failed. Every comparison succeeded, so the method returns true.

5.4 Time and Space Cost

Each pointer moves in one direction only, and together they cover the string once. So the time stays O(n).

The real win is memory. We never build a second string, so space drops to O(1). Only two integers and two characters live outside the input.

6. Dry Run of the Two Pointer Approach

Tracing the code by hand makes it stick. We do it twice here, with two different inputs. The first is deliberately clean, so you can watch the pointers move without any distraction. The second is messy, so you can watch the skip loops and the safety guard do their work.

Both traces list every loop condition in the order the code checks it. In these tables, “junk” is shorthand for any character that is not a letter or a digit.

6.1 Example One: A Straightforward Walk

We begin with s = “racecar”. This input carries no punctuation and no capital letters. So the skip loops never move anything, and the trace shows the pure two pointer rhythm on its own.

We start with left = 0 and right = 6, which is the length minus one. Here is every check in order.

Two things stand out in this clean run. Notice that both skip loops appear in every round, yet neither one ever moves a pointer. Their conditions fail immediately, because every character here is a letter.

Now look at the last row. Both pointers land on position 3, the middle letter e. That single character has no partner to face, so comparing it would prove nothing. The strict less-than test ends the loop right there, and the method returns true.

6.2 Example Two: Punctuation and Capital Letters

Now we run the messy case, s = “Ab,a!”. This one is short on purpose, yet it triggers every branch we skipped a moment ago. It holds a capital letter, a comma in the middle and an exclamation mark at the end.

Remember that we never build a cleaned copy, so these positions point into the raw text. We start with left = 0 and right = 4.

6.3 Reading the Messy Trace Closely

Three rows in that second table deserve a longer look, because they show behaviour the first example could never reveal.

Row 3 is a skip loop finally doing its job. The exclamation mark is not a letter or a digit, so right steps down from 4 to 3. Only after that does any comparison happen. Skipping always finishes before comparing.

Row 5 shows why lowercasing matters. The left pointer sits on a capital A while the right pointer sits on a small a. Compared directly they would differ, and the method would wrongly return false. Flattening both to lowercase first makes them match.

Row 9 is the most important row across both tables. The right skip loop wants to keep moving, because it already stepped onto position 1. Before moving again it checks left < right, and that check now fails since both pointers sit at 1. So the skip loop stops instead of walking past the left pointer.

Remove that guard and the pointer would keep sliding down past position 0 and off the front of the text. The next read would crash. This tiny row is exactly the bug that catches most beginners.

Row 11 ends the walk. Both pointers have now crossed, so left sits above right. That makes the outer condition fail with no comparison left undone, and the method reports true. Sure enough, the cleaned text aba reads the same in both directions.

6.4 What the Two Traces Teach Together

Put the two tables side by side and the lesson becomes clear. The clean input shows the loop skeleton: check the bounds, compare a pair, step inward, repeat. The messy input shows the guards that keep that skeleton safe on real world text.

Notice also how the two runs end differently. In “racecar” the pointers meet on a shared middle character, so left equals right. In “Ab,a!” they cross past each other, so left ends up above right. A strict less-than test handles both endings without any special case.

6.5 The Same Dry Run on Paper

The sketch puts both traces in picture form. Your clean example sits on the left and the messy one on the right, so you can compare them at a glance. Notice how the guard that halts the skip loop is called out, since that is the step most people miss. Many readers find this view easier than the tables, so use whichever one clicks for you.

7. Comparing the Two Approaches

Both approaches return the correct answer. They simply pay different prices in memory.

In an interview, mention the reverse approach first. It proves you understand the cleanup rules. Then switch to two pointers and explain that you dropped the extra copy.

That jump from O(n) space to O(1) space is the whole point of this problem. Say it out loud, because interviewers listen for exactly that sentence.

8. Common Mistakes and Edge Cases

A handful of small traps catch beginners here. Keep these in mind before you submit.

• Forgetting the guard inside the skip loops causes an out of bounds crash on text made only of punctuation.
• Filtering letters only breaks digit cases, so remember that “1a1” is a valid palindrome.
• Reversing the buffer before saving the forward copy makes both variables hold the same value, which then always returns true.
• Skipping the lowercase step makes “Aa” fail, because a capital letter and a small letter carry different stored codes.
• An empty text and a single character both return true, and the two pointer loop handles them without any special case.

9. Interview Questions

10. Conclusion

The Valid Palindrome problem in DSA looks like a beginner string question, and it is. The two pointer walk hiding inside it, however, is a real interview skill.

You will reuse this same pattern again and again. Reverse String uses it. Container With Most Water uses it. Three Sum uses it after a sort.

So take the pattern, not just the answer. Clean the input carefully, walk from both ends, and stop the moment a pair fails. Once that loop feels natural, a whole family of string and array problems opens up for you.

11. What’s Next

You now have the two pointer walk in your toolkit, so let us keep the momentum going. Here is where you came from and where you head next in this series.

• Previous: Merge Sorted Array in Java — fill the first array from the back and avoid shifting anything.
• Next up: Reverse String — swap characters in place with the same two pointer idea you just learned.

12. Further Reading

• LeetCode Valid Palindrome problem — practice the original problem and test your solution.
• Oracle Java Character documentation — the official reference for isLetterOrDigit and toLowerCase.

javahandson.com | DSA Series | Arrays & Strings