A phrase is a palindrome if, after converting uppercase letters to lowercase and removing every character that isn't a letter or digit, it reads the same forward and backward. Given a string, return whether it is a palindrome.
Before you code
Building a cleaned copy and comparing it with its reverse works, but allocates two new strings. Two indexes from the ends can skip the characters that don't count as they go.
Hints
- Start
iat 0 andjat the last index. Loop whilei < j. - If
s[i]isn't alphanumeric, advanceiand continue; likewise fors[j]. - Compare the lowercased characters. Any mismatch means False.
- A string with no letters or digits at all, such as
" ", is a palindrome.
Production & complexity notes
When solving Valid palindrome on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Two pointers on arrays to reinforce the underlying pattern.
What it practices
Two indexes moving toward each other, with a clear invariant, from Two pointers on arrays.