Problem
Ignoring case and every character that is not a letter or digit, decide whether a string reads the same forwards and backwards.
Worked examples
Input: s = "Was it a car or a cat I saw?"
Output: true
After cleaning it becomes "wasitacaroracatisaw", which is a palindrome.
Input: s = "race a car"
Output: false
Hints
Hint 1
You could build a cleaned copy, but you do not have to.
Hint 2
Put one pointer at each end and move them inward, skipping characters that do not count.
Solution approach
- Place `left` at the start and `right` at the end. Advance `left` past non-alphanumeric characters and retreat `right` likewise. Compare the two characters case-insensitively; on a mismatch return false, otherwise move both inward. If the pointers cross without a mismatch, the string is a palindrome.
- Dry-run the example, then check boundary cases before explaining time and space costs.
Complexity
O(n) time; O(1) auxiliary space.
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗