---
# System prepended metadata

title: 5. Longest Palindromic Substring
tags: [Top 100 Liked Questions, LeetCode]

---

---
tags: LeetCode,Top 100 Liked Questions
---
# 5. Longest Palindromic Substring
https://leetcode.com/problems/longest-palindromic-substring/
## 題目敘述
Given a string s, return the longest palindromic substring in s.
## Example
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"
```
## 解題想法
### 1.Z algorithm 
因Palindrome為左右對稱的string，故以每個char以及char中的空白為中心(若"abba"對稱"bb"中的空白)，左右相同就擴張
```
class Solution {
public:
string longestPalindrome(string s)
{
    int n = s.length();
    int best = 1;  //length of longest palindromic substring
    int start = 0; //begin of longest palindromic substring 

    for (int i = 0; i < n; i++) // odd length palindrome
    {
        int len = 1; //signle char is a palindrome
        int l = i - 1;
        int r = i + 1;
        while (l >= 0 && r < n && s[l] == s[r])
        {
            l--;
            r++;
            len += 2;
        }
        if (len > best)
        {
            best = len;
            start = l + 1;
        }
    }
    for (int i = 0; i < n; i++) // even length palindrome
    {
        int len = 0; 
        int l = i - 1;
        int r = i;
        while (l >= 0 && r < n && s[l] == s[r])
        {
            l--;
            r++;
            len += 2;
        }
        if (len > best)
        {
            best = len;
            start = l + 1;
        }
    }
    return s.substr(start, best);
   }
};
```
時間複雜度為O(N^2)

### 2.Bottom-up DP
參考[https://leetcode.com/problems/longest-palindromic-substring/discuss/151144/Bottom-up-DP-Logical-Thinking](https://https://leetcode.com/problems/longest-palindromic-substring/discuss/151144/Bottom-up-DP-Logical-Thinking)

DP需要三個部分

State Variable:state(s,e) //代表str[s,e]是Palindrome 從s開始e結束

Goal State:max(e-s+1) () //得到最長Palindrome

Extract Transition from Base Case Transitions:

```
for s = e, "a" is palindromic,
for s + 1 = e, "aa" is palindromic (if str[s] = str[e])
for s + 2 = e, "aba" is palindromic (if str[s] = str[e] and "b" is palindromic)
for s + 3 = e, "abba" is palindromic (if str[s] = str[e] and "bb" is palindromic)
```
於是可以推得
```
for s + n = e,str[s,e] is palindromic (if str[s] = str[e] and str[s+1,e-1] is palindromic)
```
```
class Solution {
public:
string longestPalindrome(string s)
{
    int n = s.length();
    vector<vector<bool>> dp(n,vector<bool>(n,false));
    // state[i][j] true if s[i, j] is palindrome.

    for (int i = 0; i < n; i++)
    {
        dp[i][i] = true; //base case(signle char is a palindrome)
    }

    int longestPalindrome_start = 0, longestPalindrome_len = 1;

    for (int start = n - 1; start >= 0; start--)
    {
        for (int end = start + 1; end < n; end++)
        {
            if (s[start] == s[end] && (dp[start + 1][end - 1] || (end-start)==1))
            //end-start==1 is signle char 
            {
                dp[start][end] = true;
                if (end - start + 1 > longestPalindrome_len)
                {
                    longestPalindrome_len = end - start + 1;
                    longestPalindrome_start = start;
                }
            }
        }
    }
    return s.substr(longestPalindrome_start, longestPalindrome_len);
   }
};
```
時間複雜度為O(N^2)