# \[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 ''

        max_len = 1
        left = right = 0
        for i in range(n):
            len1 = self.center_search(i, i, s)
            len2 = self.center_search(i, i + 1, s)
            len3 = max(len1, len2)
            if len3 > max_len:
                left = i - (len3 - 1) // 2
                right = i + len3 // 2
                max_len = len3
        return s[left: right + 1]

    def center_search(self, i, j, s):
        while i >= 0 and j < len(s) and s[i] == s[j]:
            i -= 1
            j += 1
        return j - i - 1
```

### 动态规划

动态规划的解法参考:

* [详细通俗的思路分析，多解法](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 - i
            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('#', '')
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/zi-fu-chuan/5-zui-chang-hui-wen-zi-chuan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.