# \[5]\[中等]\[动态规划] 最长回文子串

## 题目描述

[5. 最长回文子串](https://leetcode-cn.com/problems/longest-palindromic-substring/)

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

```
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
```

示例 2：

```
输入: "cbbd"
输出: "bb"
```

## 解题思路

### 中心扩展

回文串一定是对称的, 所以我们可以每次选择一个中心, 进行左右扩展, 判断左右字符是否相等即可.

由于存在对称中心是**奇数**或**偶数**的情况, 所有共有$$2N - 1$$个中心, $$N$$是字符串的长度.

这种方法是比较直观的方法, 时间复杂度$$O(N^2)$$, 空间复杂度$$O(1)$$

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ''

        string = '#' + '#'.join(list(s)) + '#'
        n = len(string)
        p = []
        center, right = -1, -1
        mcenter, mrad = -1, -1
        for i in range(n):
            cur = 0
            mirror = 2 * center - right
            if i < right and mirror >= 0:  # 当前位置已经超出了最右的位置, 需要重新以当前位置为中心, 向外搜索
                cur = min(right - i, p[mirror])

            while i - cur - 1 >= 0 and i + cur + 1 < n and string[i - cur - 1] == string[i + cur + 1]:
                cur += 1

            if i + cur > right:
                right = i + cur
                center = i

            if cur > mrad:
                mcenter = i
                mrad = cur
            p.append(cur)

        return string[mcenter - mrad: mcenter + mrad].replace('#', '')
```

### 动态规划

动态规划的解法参考:

* [详细通俗的思路分析，多解法](https://leetcode-cn.com/problems/longest-palindromic-substring/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-bao-gu/)
* [动态规划、中心扩散、Manacher 算法](https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/)

第一篇对动态规划的**状态**, **状态转移方程**, **边际条件**描述的更清楚, 并且考虑了**空间优化**的问题, 降低了空间复杂度.

第二篇详细讲解了, 根据状态转移方程的特点, 迭代的方向的选择及其原因, 也为第一篇文中的空间优化的循环方式, 做了更为清晰的解释.

此题采用动态规划的思路, 空间复杂度为$$O(n^2)$$, 下面的代码为空间优化的版本, 对应的空间复杂度为$$O(n)$$.

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ''

        p = [False] * n
        cur_start, cur_length = 0, 1
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, i - 1, -1):
                t = False
                if j - i > 1 and p[j - 1] and s[i] == s[j]:
                    t = True
                elif j - i == 1 and s[i] == s[j]:
                    t = True
                elif j == i:
                    t = True
                elif j < i:
                    break

                p[j] = t
                if t and (j - i + 1) > cur_length:
                    cur_start = i
                    cur_length = j - i + 1
        return s[cur_start: cur_start + cur_length]
```

### Manacher Algorithm

Manacher算法参考[详细通俗的思路分析，多解法](https://leetcode-cn.com/problems/longest-palindromic-substring/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-bao-gu/).

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ''

        string = '#' + '#'.join(list(s)) + '#'
        n = len(string)
        p = []
        center, right = -1, -1
        for i in range(n):
            cur = 0
            mirror = 2 * center - right
            if i < right and mirror >= 0:  # 当前位置已经超出了最右的位置, 需要重新以当前位置为中心, 向外搜索
                cur = min(right - i, p[mirror])

            while i - cur - 1 >= 0 and i + cur + 1 < n and string[i - cur - 1] == string[i + cur + 1]:
                cur += 1

            if i + cur > right:
                right = i + cur
                center = i
            p.append(cur)

        center, rad = max([(i, t) for i, t in enumerate(p)], key=lambda x: x[1])
        return string[center - rad: center + rad].replace('#', '')
```