# Longest Palindromic Substring

## Question ([LC.5](https://leetcode.com/problems/longest-palindromic-substring/description/))

> Given a string, find the longest palindromic substring.

## Example

```
I: "babad"
O: "bab" or "aba"
I: "cbbd"
O: "bb"
```

## Brute Force Search

```
maintain a global max

for all substring O(n^2)
    check isPalindrome(substring) O(n)
```

time O(n^3) space O(1)

## DP by Substring

We can memoize the inner substring ex. "aba" => "babad"

![](https://3556266963-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtpqP4Bii7DT_BTd4fN%2F-LtpqQ7GPCPppH_fyCKt%2F-LtpqYONoMvvloLbmFaf%2Fpalindrome%20dp.jpg?generation=1573935266956456\&alt=media)

```
1. define optimal subproblem
P(i,j) = whether S[i:j] is a palindrome 

2. solve by substring
P(i,j) = P(i+1,j-1) and S[i] == S[j]

3. base cases
for i from 0 to n-1
    P(i,i) = true // first layer
for i from 0 to n-2
    P(i,i+1) = S[i] == S[i+1] // second layer

4. topo order
always increasing substring size (in this case diagonally)
for len from 3 to n
    for i from 0 to n-len
        j = i + len - 1

5. final answer
global max
```

## Code

```java
public String longestPalindrome(String str) {
    // sanity check
    if (str == null || str.length() <= 1) {
        return str;
    }
    int n = str.length();
    // create memo table
    boolean[][] memo = new boolean[n][n];
    // init base case (two layers cause tabulating diagonally)
    for (int i = 0; i < n; i++) {
        memo[i][i] = true;
    }
    for (int i = 0; i < n - 1; i++) {
         memo[i][i+1] = str.charAt(i) == str.charAt(i+1);
    }
    // topo order        
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            memo[i][j] = memo[i+1][j-1] && str.charAt(i) == str.charAt(j);
        }
    }
    // find max
    int maxI = 0, maxJ = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (memo[i][j] && j-i > maxJ - maxI) {
                maxI = i;
                maxJ = j;
            }                
        }
    }
    // return max
    return str.substring(maxI, maxJ + 1);
}
```

Time O(n^2) Space O(n^2)

## Middle-out Expansion

There are $$2n - 1$$ centers in a length $$n$$ string. Expanding them out from there.

Time 2n \* n = O(n^2) Space O(1)