# Longest Palindromic Substrings
https://leetcode.com/problems/longest-palindromic-substring/
## Approach 1: Brute Force
```python
def check(i, j):
left = i
right = j - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
for length in range(len(s), 0, -1):
for start in range(len(s) - length + 1):
if check(start, start + length):
return s[start : start + length]
return ""
```
- Complexity: $O(n^3)$
## Approach 2: [[dp|DP]]
```python
n = len(s)
dp = [[False] * n for _ in range(n)]
ans = [0, 0]
for i in range(n):
dp[i][i] = True
for i in range(n - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
ans = [i, i + 1]
for diff in range(2, n):
for i in range(n - diff):
j = i + diff
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
ans = [i, j]
i, j = ans
return s[i : j + 1]
```
- Intuition
- Check palindrome from center to edges
- All characters are palindromes of length 1.
- Consecutive identical characters are palindromes of length 2.
- `dp[i][j] = True` indicates that `s[i:j + 1]` is a palindrome
- Longer palindromes can only be formed by shorter palindromes
- Time: $O(n^2)$, space $O(n^2)$
## Approach 3: Iterative
Focus on the center, and expand from it, only $O(n)$ centers to consider.
```python
def expand(i, j):
left = i
right = j
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
ans = [0, 0]
for i in range(len(s)):
odd_length = expand(i, i)
if odd_length > ans[1] - ans[0] + 1:
dist = odd_length // 2
ans = [i - dist, i + dist]
even_length = expand(i, i + 1)
if even_length > ans[1] - ans[0] + 1:
dist = (even_length // 2) - 1
ans = [i - dist, i + 1 + dist]
i, j = ans
return s[i : j + 1]
```
$O(n^2)$ time, but faster than approach 2 since most characters do not form a palindrome; $O(n)$ space.