# 0005. Longest Palindromic Substring

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0005-longest-palindromic-substring)

Given a string `s`, return *the longest palindromic substring* in `s`.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `1 <= s.length <= 1000`
* `s` consist of only digits and English letters.

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

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

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

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Whether a string is palindromic **depends on the previous two chars** from the left and right. Thus, we could **adopt dynamic programming with a memo** to solve this problem.
{% endhint %}

A **two-dimension array** is initialized to store **whether `s[j:i]` is a palindromic string** by recording as **`dp[i][j] = True`**. Then, we iterate the input string by a **nested for loop** which range is from `i = len(s)` and `j = i+1`.&#x20;

In each iteration, there are **three different conditions** to help us check palindrome:

1. **`if i == j`**, `dp[i][j] = True`&#x20;
2. **`if i == j + 1`**, `dp[i][j] = s[i] == s[j]`
3. **`else`**, **`dp[i][j] = (dp[i-1][j+1] and s[i] == s[j])`**

{% hint style="warning" %}
Note that **condition 3** checks **whether the shrunk string `s[j+1:i-1]` is a palindrome string** and whether **`s[i] == s[j]`**
{% endhint %}
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3 (DP)" %}

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # (base case)
        if len(s) < 2: return s

        # ==================================================
        #  Dynamic Programming                             =
        # ==================================================
        # time  : O(n^2)
        # space : O(n^2)
        
        ret = ''
        
        # dp[i][j] = True mean s[j:i] = Palindrome
        dp = [[None] * len(s) for i in range(len(s))]
        
        for i in range(len(s)):
            for j in range(i+1):
                if i == j: dp[i][j] = True
                elif i == j+1: dp[i][j] = s[i] == s[j]
                else: dp[i][j] = (dp[i-1][j+1] and s[i] == s[j])
                
                if dp[i][j] and i - j + 1 > len(ret): ret = s[j:i+1]
                    
        return ret
```

{% endtab %}

{% tab title="🤖 Python3 (non-DP)" %}

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # (base case)
        if len(s) < 2: return s
        
        # ==================================================
        #  Expand around Corner                            =
        # ==================================================
        # time  : O(n^2)
        # space : O(1)
        
        self.ret = ''
        self.maxLen = 0
        
        for i in range(len(s)):
            # ODD length (aabbdde -> [a'a'b]bdde, a[a'b'd], ..., aabb[d'd'e])
            self.expand(s, i, i)

            # EVEN length (aabbdde -> [a'a']bbdde, a[a'b']bdde, ..., aabbd[d'e'])
            self.expand(s, i, i + 1)
            
        return self.ret
    
    def expand(self, s: str, l: int, r: int) -> None:
        while l >=0 and r < len(s) and s[l] == s[r]:
            if(r - l + 1) > self.maxLen:
                self.ret = s[l:r+1]
                self.maxLen = len(self.ret)
            l -= 1
            r += 1
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
```

{% endtab %}
{% endtabs %}