O(N^2)으로 풀었는데, 놀랍게도 선형시간 풀이가 있습니다. Manacher's algorithm이라고 부르네요.

Given a string s, return the longestpalindromicsubstring in s.

Example 1:

Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer. 

Example 2:

Input: s = "cbbd" Output: "bb" 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.