Solving the Valid Palindrome Problem in Java

Hey there! If you’re prepping for coding interviews or just love a good string problem, you’ve probably come across the Valid Palindrome challenge. It’s a classic that tests your ability to manipulate strings and think logically. Today, I’ll walk you through solving LeetCode’s “125. Valid Palindrome” problem in Java using a slick two-pointer approach. Let’s dive in! The Problem Here’s the problem straight from LeetCode: 125. Valid Palindrome 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. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise. Examples Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: After cleaning, it becomes "amanaplanacanalpanama", which is a palindrome. Input: s = "race a car" Output: false Explanation: After cleaning, it’s "raceacar", which isn’t a palindrome. Input: s = " " Output: true Explanation: After removing non-alphanumeric characters, it’s an empty string "", which reads the same both ways. Constraints 1

Mar 13, 2025 - 10:39

Solving the Valid Palindrome Problem in Java

Hey there! If you’re prepping for coding interviews or just love a good string problem, you’ve probably come across the Valid Palindrome challenge. It’s a classic that tests your ability to manipulate strings and think logically. Today, I’ll walk you through solving LeetCode’s “125. Valid Palindrome” problem in Java using a slick two-pointer approach. Let’s dive in!

The Problem

Here’s the problem straight from LeetCode:

125. Valid Palindrome

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. Alphanumeric characters include letters and numbers.

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

Examples

Input: s = "A man, a plan, a canal: Panama"

Output: true

Explanation: After cleaning, it becomes "amanaplanacanalpanama", which is a palindrome.
Input: s = "race a car"

Output: false

Explanation: After cleaning, it’s "raceacar", which isn’t a palindrome.
Input: s = " "

Output: true

Explanation: After removing non-alphanumeric characters, it’s an empty string "", which reads the same both ways.

Constraints

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

The goal? Ignore spaces, punctuation, and case, then check if the cleaned string is a palindrome. Sounds fun, right?

My Approach: Two Pointers

There are a few ways to tackle this, but I went with a two-pointer technique because it’s efficient and doesn’t need extra space. The idea is simple: start with one pointer at the beginning (i) and one at the end (j), then move them toward each other. Along the way, skip non-alphanumeric characters and compare the rest, ignoring case. If all pairs match, it’s a palindrome!

Here’s why I like this:

Time Complexity: O(n) — we only scan the string once.
Space Complexity: O(1) — no extra arrays or strings needed.

Let’s see it in action.

The Code

Here’s my solution in Java:

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;

        if (s.isEmpty()) {
            return true;
        }

        while (i < j) {        
            char left = s.charAt(i);
            char right = s.charAt(j);

            // Skip if left isn’t alphanumeric
            if (!('0' <= left && left <= '9' || 'a' <= left && left <= 'z' || 'A' <= left && left <= 'Z')) {
                i++;
                continue;
            }
            // Skip if right isn’t alphanumeric
            if (!('0' <= right && right <= '9' || 'a' <= right && right <= 'z' || 'A' <= right && right <= 'Z')) {
                j--;
                continue;
            }
            // Compare characters (case-insensitive)
            if (left == right || Character.toLowerCase(left) == Character.toLowerCase(right)) {
                i++; 
                j--;    
                continue;
            }
            return false;
        }
        return true; 
    }
}

How It Works

Setup Pointers:
- i starts at 0, j starts at the end of the string.
- If the string’s empty, return true (though the constraints guarantee at least 1 character, I added this for clarity).
Main Loop:
- Grab the characters at i (left) and j (right).
- Skip Junk: If left isn’t a letter or number, increment i. Same for right with j.
- Compare: If both are alphanumeric, check if they match (either directly or after converting to lowercase). If they do, move the pointers inward. If not, return false.
- Finish: If the loop ends (i.e., i >= j), all checks passed, so return true.

Walking Through an Example

Let’s run it on "A man, a plan, a canal: Panama":

Cleaned version (for reference): "amanaplanacanalpanama".
Step-by-step:
- i = 0 ('A'), j = 30 ('a'): A becomes a, matches a. Move to i = 1, j = 29.
- i = 1 (' '), j = 29 ('m'): Skip space, i = 2.
- i = 2 ('m'), j = 29 ('m'): Match! i = 3, j = 28.
- Fast-forward past spaces, commas, and colons…
- Eventually, i and j meet in the middle, and all pairs match.
Result: true.

Try "race a car" yourself — you’ll see it fails at 'e' vs. 'r'.

Complexity Analysis

Time Complexity: O(n). We visit each character at most once, even with skips.
Space Complexity: O(1). Just a couple of pointers and variables—no big data structures.

Refining the Solution

My original code works, but it’s a bit verbose. Here’s a cleaner version using Java’s built-in methods:

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;

        while (i < j) {
            char left = s.charAt(i);
            char right = s.charAt(j);

            if (!Character.isLetterOrDigit(left)) {
                i++;
            } else if (!Character.isLetterOrDigit(right)) {
                j--;
            } else {
                if (Character.toLowerCase(left) != Character.toLowerCase(right)) {
                    return false;
                }
                i++;
                j--;
            }
        }
        return true;
    }
}

Changes:

Swapped manual range checks for Character.isLetterOrDigit()—more readable!
Simplified the flow by handling the comparison in an else block.

Both versions work, but this one’s easier on the eyes.

Alternative Approaches

You could also solve this by:

Cleaning First: Use regex (e.g., s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase()) to get a clean string, then check if it’s a palindrome.
- Pros: Simpler logic.
- Cons: O(n) space for the new string.
Reverse and Compare: Clean the string, reverse it, and check equality.
- Cons: Same space issue.

The two-pointer method wins for efficiency in interviews!

Conclusion

And there you have it—a solid solution to the Valid Palindrome problem! We used two pointers to check the string in-place, skipping non-alphanumeric characters and handling case-insensitivity on the fly. It’s fast, lean, and perfect for impressing interviewers.

Try running this code on your own test cases—like "0P" or ".,"—and see how it holds up. Let me know in the comments if you’ve got questions or a cool twist on this problem. Happy coding!