Longest Palindromic Substring (Manacher's Algorithm)

Longest Palindromic Substring Given a string s, return its longest contiguous palindromic substring. A palindrome reads the same forward and backward. If multiple longest palindromic substrings exist, return any one of them. Design an algorithm with O(n) time complexity. Input Format One line containing the string s. Output Format Print any longest palindromic substring of s. Constraints 1 <= len(s) <= 2 * 10^5 s contains comparable characters, such as English letters and digits. Example Input: babad Output: bab aba is also a valid answer. Example Input babad Output bab