给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
提示：
-
1 <= s.length <= 1000 -
s仅由数字和英文字母组成
最简单的方式：使用两个指针，把字符串逐个"拆成"子串，然后留下最大子串即可。可惜，这种算法的时间复杂度是 O(n3)。
中心扩散法
没想到，竟然存在时间复杂度为 O(n) 的算法：Manacher’s Algorithm。在维基百科上有解释： Longest palindromic substring - Wikipedia。回头研究研究再补充！
另外，这道题还可以练手动态规划。
- 一刷
-
link:{sourcedir}/_0005_LongestPalindromicSubstring.java[role=include] - 二刷
-
link:{sourcedir}/_0005_LongestPalindromicSubstring_2.java[role=include] - 三刷
-
link:{sourcedir}/_0005_LongestPalindromicSubstring_3.java[role=include]
-
Manacher’s Algorithm - Linear Time Longest Palindromic Substring - Part 1
-
Manacher’s Algorithm - Linear Time Longest Palindromic Substring - Part 2
-
Manacher’s Algorithm - Linear Time Longest Palindromic Substring - Part 3
-
Manacher’s Algorithm - Linear Time Longest Palindromic Substring - Part 4
-
Manacher’s Algorithm Explained— Longest Palindromic Substring