# LC 5. Longest Palindromic Substring

### [Problem link](https://leetcode.com/problems/longest-palindromic-substring/)

###### tags: `leedcode` `python` `c++` `medium` `Two Pointer` `DP`

Given a string <code>s</code>, return the **longest palindromic substring** in <code>s</code>.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

- <code>1 <= s.length <= 1000</code>
- <code>s</code> consist of only digits and English letters.

## Solution 1 - Two Pointer
#### Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        max_left, max_right = 0, 0

        def logest_pali_substr(left, right):
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1
                right += 1
            return left + 1, right - 1

        for i in range(n):
            left, right = logest_pali_substr(i, i)
            if right - left + 1 > max_right - max_left + 1:
                max_left = left
                max_right = right
            
            left, right = logest_pali_substr(i, i + 1)
            if right - left + 1 > max_right - max_left + 1:
                max_left = left
                max_right = right

        return s[max_left : max_right + 1]

#### C++

class Solution {
public:
    int getLongestPalindromeLen(string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    string longestPalindrome(string s) {
        int base = 0;
        int len = 1;
        for (int i = 0; i < s.size(); i++) {
            int odd = getLongestPalindromeLen(s, i, i);
            int even = getLongestPalindromeLen(s, i, i + 1);
            int maxLen = max(odd, even);
            if (maxLen > len) {
                base = i - (maxLen - 1) / 2;
                len = maxLen;
            }
        }
        return s.substr(base, len);
    }
};

## Solution 2 - DP
#### Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        left = 0
        right = 0
        dp = [[False] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j]:
                    if j - i <= 1 or dp[i + 1][j - 1]:
                        dp[i][j] = True
                        if j - i + 1 > right - left + 1:
                            left = i
                            right = j

        return s[left : right + 1]

#### C++

class Solution {
public:
    string longestPalindrome(string s) {
        int maxLen = 1;
        int left = 0;
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));

        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i >= 2) {
                        dp[i][j] = dp[i + 1][j - 1];
                    } else {
                        dp[i][j] = true;
                    }
                    if (dp[i][j] && j - i + 1 > maxLen) {
                        left = i;
                        maxLen = j - i + 1;
                    }
                }
            }
        }
        return s.substr(left, maxLen);
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O($n^2$) | O(1) |
>| Solution 1 | O($n^2$) | O($n^2$) |

## Note
與[LC 647. Palindromic Substrings](https://hackmd.io/@Alone0506/B1FMTgk92)類似