113. Valid Palindrome

A palindrome reads the same from both ends, so walk one pointer in from the left and one in from the right, skipping anything that isn't a letter or digit, and compare the characters they land on.

Idea

A palindrome mirrors around its center: the first meaningful character must equal the last, the second must equal the second-to-last, and so on. Instead of building a cleaned copy of the string (which costs O(n) extra space), we scan inward from both ends at once and simply ignore characters that don't count.

Algorithm

1. Put pointer i at the start and j at the end.
2. While i < j:
   • Advance i rightward while s[i] is not alphanumeric.
   • Advance j leftward while s[j] is not alphanumeric.
   • Compare s[i] and s[j] case-insensitively. If they differ, it is not a palindrome — return false.
   • Otherwise step both pointers inward (i += 1, j -= 1).
3. If the pointers cross without a mismatch, every mirrored pair matched — return true.

Worked example: "A man, a plan, a canal: Panama"

• i starts on A, j starts on the last a. Lowercased, a == a ✓ → move inward.
• i skips the space and lands on m; j skips :, space and lands on m. m == m ✓.
• Continuing inward, every alphanumeric pair matches (a=a, n=n, a=a, ...). The comma, colon, and spaces are all skipped and never compared.
• The pointers meet in the middle with no mismatch → return true.

Contrast with "race a car": after skipping spaces the pointers reach r (left) vs r (right) ✓, then a/a ✓, then c/c ✓, then e (left) vs a (right) ✗ → return false.

Complexity

• Time: O(n) — each pointer moves inward at most n steps total, so we touch each character a constant number of times.
• Space: O(1) — only two integer indices; the string is never copied.

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            while (i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
            while (i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
            if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}