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

# LeetCode 5. Longest Palindromic Substring

Given a string `s`, return *the longest palindromic substring* in `s`.

**Example 1:**

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

**Example 2:**

```
Input: s = "cbbd"
Output: "bb"
```

**Example 3:**

```
Input: s = "a"
Output: "a"
```

**Example 4:**

```
Input: s = "ac"
Output: "a"
```

**Constraints:**

* `1 <= s.length <= 1000`
* `s` consist of only digits and English letters (lower-case and/or upper-case),

## Solution:

[English Version in Youtube](https://youtu.be/l0FR5x5dNvs)

[中文版解答Youtube Link](https://youtu.be/7jkLvTSyyy4)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV12541177cx/)

```
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        int longestBegin = 0;
        int maxLen = 1;
        vector<vector<bool>> table(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++)
            table[i][i] = true;
  
        for (int i = 0; i < n-1; i++) {
            if (s[i] == s[i+1]) {
                table[i][i+1] = true;
                longestBegin = i;
                maxLen = 2;
            }
        }
  
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                if (s[i] == s[j] && table[i+1][j-1]) {
                    table[i][j] = true;
                    longestBegin = i;
                    maxLen = len;
                }
            }
        }
        return s.substr(longestBegin, maxLen);
    }
};
```