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

# Longest Palindromic Substring

## Problem

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

{% hint style="info" %}
For example:

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

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

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

{% endhint %}

### Thought Process

* Make a boolean matric to see which left to right indices equal a palindrome

* Make a variable *maxLength* and change this variable if $$j-i>maxLength$$ 

## Solution

```
class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[False for j in range(len(s))] for i in range(len(s))]
        
        ans = ''
        
        for i in range(len(s)):
            dp[i][i] = True
            ans = s[i]

        maxL = -1
        for i in range(len(s)-1,-1,-1):
            for j in range(i+1,len(s)):
                if s[i] == s[j]:
                    if j-i == 1 or dp[i+1][j-1] == True:
                        dp[i][j] = True
                        if j-i > maxL:
                            maxL = j-i
                            ans = s[i:j+1]
                            
        return(ans)

#Time: O(n^2)
#Space: O(n^2)
```