Algorithms and Data Structures · Junior · Question 43 of 75
How do you check whether a string is a palindrome in O(n) time and O(1) extra space?
- 1Sort the characters and compare with the original
- ✓Correct answer: Compare characters from both ends moving toward the middle
- 3Compare the string with
str.split("").reverse().join("")
Explanation
Two pointers compare s[i] with s[j] and stop at the first mismatch. Reversing works too but creates a new string, so it uses O(n) memory. Sorting is wrong: it loses the order of characters.