125. Valid Palindrome

The naive read of this problem is “strip the junk, lowercase it, then compare the string to its reverse.” That works, but it allocates a whole second string. The two-pointer version does the same check in place, in $O(1)$ extra space.

Question

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.

• Example1

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

• Example2

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

• Example3

Input: s = " "
Output: true
Explanation:
s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

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

Answer

// TC: O(n)
// SC: O(1)
public boolean isPalindrome(String s) {
    if (s == null) return false;
    int left = 0, 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--;
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Two pointers that skip the junk

The outer loop walks left in from the front and right in from the back. The two inner while loops are the whole idea: before each comparison, they fast-forward each pointer past anything that isn’t a letter or digit. So for "A man, a plan...", the spaces and commas are stepped over silently, and only real characters ever get compared — lowercased on the spot with Character.toLowerCase. It’s the standard two-pointer shape, with a filter bolted onto each side.

The left < right guard inside the inner loops matters. Without it, an all-punctuation string like ".," would walk left straight past right and off the end of the string. (The single-space example " " doesn’t need the inner guard — it’s caught earlier, because the outer while (left < right) never runs when the string collapses to length 1.)

Why not just clean the string first?

Building "amanaplanacanalpanama" and comparing it to its reverse is easier to write and, honestly, fine in most real code. The reason the two-pointer version is the interview answer is space: the cleaned-string approach is $O(n)$ extra memory, while walking inward from both ends stays $O(1)$. Same $O(n)$ time either way — you still touch every character once — but no allocation. When an interviewer asks “can you do it without extra space?”, this is the pivot they’re after.

References

• https://leetcode.com/problems/valid-palindrome/