Longest Palindrome string

• discovered by Glenn K. Manacher in 1975

Steps

• Preprocess the string with a sentinel: O(n)
• Start processing the string from left to right
• keep track of the palindrome that reaches to the farthest right and is the largest to reach that far right
• when iterating elements check if current character belongs to that large palindrome
• if it does then we can fill in the values, if it is at the edge we can populate initial value