Problem: Given a string, find a longest palindrome substring.
Solution: We can use general suffix tree that stores the original string and its reverse, which is an O(N) algorithm. However, here we give a better one with less space overhead while still O(N) complexity. This algorithm is called Manacher's algorithm. If we check a string from left to right, we can leverage the palindrome check we did previously. This is from the symmetry of palindrome.
Read full article from Tristan's Collection of Interview Questions: The Longest Palindrome Substring (Manacher's algorithm)
