最长回文子串
Longest Palindromic Substring
题目详情
问题：最长回文子串
考察：字符串、动态规划
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/longest-palindromic-substring/
Given a string s, return the longest palindromic substring 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 <= 1000sconsist of only digits and English letters.
解析
思路：枚举每个可能中心，分别处理奇数长度和偶数长度回文，向两侧扩展并记录最长区间。也可以用 DP，但中心扩展更简单。
复杂度：时间 O(n^2)，空间 O(1)。