> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/zhong-yu-shua-dao-100-dao-le-wo-shi-fen-shui-ling/bu-chong-120-dao/5.-longest-palindromic-substring.md).

# 5. Longest Palindromic Substring

### Solution 1: radical extend

{% hint style="info" %}
Check the longest palindromic substring when central element is from s\[0] to s\[n]. Use two pointers left and right to track the two edge element of the palindromic.

从第一个到最后一个元素，尝试作为中心的元素，最长回文字符串分奇数和偶数。
{% endhint %}

{% tabs %}
{% tab title="Python" %}

```python
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        
        # edge case
        if len(s) <= 1:
            return s
        
        # regular case
        res = []
        res_len = 0
        for i in range(len(s)):
            left, right = i, i
            # if the longest palindromic substring is odd, 奇数
            while left >=0 and right < len(s) and s[left] == s[right]:
                if right - left + 1 > res_len:
                    res = s[left:right+1]
                    res_len = right - left + 1
                left -= 1
                right += 1
            
            # if the longest palindromic substring is even，偶数
            left, right = i, i+1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if right - left + 1 > res_len:
                    res = s[left:right+1]
                    res_len = right - left + 1
                left -= 1
                right += 1
                
        return res
```

{% endtab %}
{% endtabs %}

Time complexity = $$O(n^2)$$ , space complexity = $$O(n)$$ .

### Solution 2: Dynamic Programming

Use `dp[i][j]` to record from `i` to `j` is Palion or not. Key idea is: if s\[i] = s\[j] and dp\[i+1]\[j-1] is Palion, then dp\[i]\[j] is Palion.

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[False]*len(s) for i in range(len(s))]
        output  = ''
        
        for end in range(len(s)):
            for start in range(end+1):
                if s[start] == s[end]:
                    l = end - start + 1
                    if l < 3 or dp[start+1][end-1]:
                        dp[start][end] = True
                    
                    if l > len(output) and dp[start][end]:
                        output = s[start:end+1]
        return output
```

T = $$O(n^2)$$ , S = $$O(n^2)$$&#x20;