LeetCode 125 · Easy · Two Pointers

Valid Palindrome

Given a string s, return true if it reads the same forward and backward after lowercasing it and dropping every character that is not a letter or digit.

O(n)time
O(1)space
2 endsmove inward

printable ASCII · 1–40 characters · spaces and punctuation are kept

public boolean isPalindrome(String s) { int l = 0; int r = s.length() - 1; while (l < r) { while (l < r && !Character.isLetterOrDigit(s.charAt(l))) { l++; } while (l < r && !Character.isLetterOrDigit(s.charAt(r))) { r--; } if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) { return false; } l++; // pair matched, move inward r--; } return true;}
l
—
r
—
s.charAt(l)
—
s.charAt(r)
—
pairs matched
0

Why it works

  1. Brute force builds the cleaned string (lowercase, letters and digits only) and compares it with its reverse. Also O(n), but it copies the string: O(n) extra space.
  2. Two pointers compare in place. Invariant: every letter outside [l, r] already matches its mirror. Each match moves both ends inward, so the unchecked middle shrinks by 2.
  3. Skip, don't delete. The inner loops hop over spaces and punctuation. Nested loops, yet every index is visited at most once: O(n) time, O(1) space.
  4. Pitfall: keep l < r in the inner loops, or a string like ".," runs a pointer off the end. And Character.isLetterOrDigit includes digits: "0P" is not a palindrome.
  5. Exit early: the first mismatch answers the question. The characters between the pointers are never read.
  6. Follow-up, Valid Palindrome II (680): you may delete one character. At the first mismatch, try skipping s.charAt(l) or s.charAt(r) and check the rest with the same two pointers.