> For the complete documentation index, see [llms.txt](https://zhongwen.gitbook.io/leetcode-report/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhongwen.gitbook.io/leetcode-report/medium/5.-longest-palindromic-substring.md).

# 5. Longest Palindromic Substring

Given a string **s**, find the longest palindromic substring in **s**. You may assume that the maximum length of **s** is 1000.

**Example 1:**

```
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
```

**Example 2:**

```
Input: "cbbd"
Output: "bb"
```

#### 解题要点：

一个dp 2d array来存i，j是否为回文，同时在遍历时需要检测头尾是否为一样字符，里面的字符是否为回文（长度小于等于2的默认为回文），如果是，把当前dp位置的i，j改为True，此位置是回文，并记录最大回文index，最后返回记录好的index。

```python
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if s == None or len(s) <= 1:
            return s
        dp = [[0] * len(s) for i in range(len(s))]
        left, right = 0, 0
        for j in range(1, len(s)):
            for i in range(0, j):
                if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1] == 1):
                    dp[i][j] = 1
                    if j - i > right - left:
                        left = i
                        right = j
        return s[left:right+1]
```