Valid Palindrome

What the problem is really asking

We need to ignore punctuation, spaces, and case, then check whether the cleaned string reads the same forward and backward.

Intuition

This is a perfect two-pointer problem.

One pointer starts from the left, the other from the right. If a character does not matter, skip it. If both matter, compare them.

Brute-force idea

The simpler approach is:

• build a new string containing only lowercase letters and digits
• reverse it
• compare the two

That works, but it uses extra space.

Optimized approach

Use two pointers directly on the original string.

At each step:

1. move left until it points to an alphanumeric character
2. move right the same way
3. compare both characters ignoring case
4. if they differ, return false

If the pointers finish without a mismatch, the string is a palindrome.

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

            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}

Dry run

Take s = "A man, a plan, a canal: Panama".

• A matches a
• skip spaces and punctuation
• m matches m
• continue inward

Every meaningful character matches, so the answer is true.

Common mistakes

1. Forgetting to skip non-alphanumeric characters

Then punctuation will cause false mismatches.

2. Comparing without normalizing case

A and a should be treated as equal.

3. Building a cleaned copy when not needed

That is acceptable, but the in-place two-pointer version is cleaner and more space-efficient.

Complexity

Time Complexity: O(n)

Space Complexity: O(1)