问题描述
给定一个字符串 s，找出其中最长的回文子字符串，假设 s 的最大长度为 1000。
例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是正确的答案
例 2：
Input: "cbbd"
Output: "bb"
问题难度
Medium
解题思路
注意到回文的对称性特点，我们只需要在遍历 s 的过程中，假设每一个字符都是回文的中心，对于每一个回文中心，我们不断向两边扩展，同时检测其对称性，找出该回文的边界，并记录其长度，最终，当遍历完 s 之后，我们便检测了 s 中所有的回文，当然就可以得到 s 中最长的回文子字符串。这种方法的时间复杂度为 。
需要注意的是，回文有两种形式：单中心和双中心，所以我们在遍历每个字符时，不仅要把当前字符当做单中心回文的中心，还要将当前字符和下一个字符当做双中心回文的中心，并分别以这两个中心向两边扩展。
全部代码如下：
class Solution():
def expand(self, left, right, s):
"""
expand from middle point
"""
if right >= len(s) or s[left] != s[right]:
return 0
while left-1 >= 0 and right+1 < len(s) and s[left-1] == s[right+1]:
left -= 1
right += 1
return right + 1 - left
def longest_palindrome(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return ""
middle = 0
max_len = 0
for i in range(len(s)):
len1 = self.expand(i, i, s)
len2 = self.expand(i, i+1, s)
longer = max(len1, len2)
if longer > max_len:
max_len = longer
middle = i
begin = middle-int((max_len-1)/2)
return s[begin:begin+max_len]
