Problem intuition
- The naive route is to clean the string and compare it with its reverse.
- The more memory-efficient version keeps two pointers at the ends and skips every character that does not matter.
Solution
The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.
Solution 1
Normalize and reverse
- Build a cleaned lowercase string first, then compare it with its reverse.
- This is a clear idea, but it spends extra memory.
- Time complexity: O(n)
- you scan the string to build the cleaned version and compare the normalized result in linear time.
- Space complexity: O(n)
- the cleaned string and reversed copy both scale with the input length.
Solution 2
Two pointers in place
- Walk from both ends of the string.
- Skip non-alphanumeric characters and compare meaningful characters only.
- Time complexity: O(n)
- the left and right pointers each move toward the center without revisiting characters.
- Space complexity: O(1)
- the string is checked in place using only pointer variables and a few temporary characters.