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.
Given a string s, return true if it is a palindrome, or false otherwise.
Example 1
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2
Input: s = "race a car"
Output: false
1 <= s.length <= 2*10^5Two pointers from both ends, skipping non-alphanumeric characters as you go — no need to build a separate cleaned string first.
A simpler-to-write brute force: build a fully cleaned, lowercased copy of the string, then compare it directly against its own reverse — correct, but costs O(n) extra space the two-pointer version avoids entirely.
public boolean isPalindromeBruteForce(String s) {
StringBuilder cleaned = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) cleaned.append(Character.toLowerCase(c));
}
String forward = cleaned.toString();
String backward = cleaned.reverse().toString();
return forward.equals(backward);
}Time: O(n) · Space: O(n) for the cleaned/reversed strings