The tell: Compare a sequence against its reverse, in place, ignoring some characters.
How you get there
1Walk one pointer from each end toward the middle.
2Skip anything that is not alphanumeric rather than building a cleaned copy.
3Compare lowercased characters; mismatch means not a palindrome.
Solution
Python
def is_palindrome(s: str) -> bool:
lo, hi = 0, len(s) - 1
while lo < hi:
while lo < hi and not s[lo].isalnum():
lo += 1
while lo < hi and not s[hi].isalnum():
hi -= 1
if s[lo].lower() != s[hi].lower():
return False
lo += 1
hi -= 1
return True
Time
O(n)
Space
O(1)
What goes wrong
Omitting `lo < hi` inside the skip loops runs off the end on an all-punctuation string.