Longest Palindromic Substring

Question (LC.5)

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"

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

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)