Reference: LeetCode
Difficulty: Medium

My Post: Java DP Solutions with Illustration T_T

Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example: 

1
2
3
4
5
6
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

Analysis

Brute-Force

For each character i, we examine all substrings starting from index i and check if they are palindromic.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public String longestPalindrome(String s) {
  if (s == null || s.length() == 0) {
    return "";
  }
  int n = s.length();
  String maxStr = "";
  for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) {
      if (isValid(s, i, j) == true) {
        if (j - i + 1 > maxStr.length()) { // update maxStr
          maxStr = s.substring(i, j + 1);
        }
      }
    }
  }
  return maxStr;
}

private boolean isValid(String s, int lo, int hi) {
  int n = hi - lo + 1;
  for (int i = 0; i < n / 2; ++i) {
    if (s.charAt(lo + i) != s.charAt(hi - i)) {
      return false;
    }
  }
  return true;
}

Time: $O(N^3)$
Space: $O(1)$

Expansion From the Center

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public String longestPalindrome(String s) {
  if (s == null || s.length() == 0) {
    return "";
  }
  int n = s.length();
  StringBuilder longest = new StringBuilder();
  for (int i = 0; i < n; ++i) {
    findPalindrome(s, i, i, longest); // odd
    findPalindrome(s, i, i + 1, longest); // even
  }
  return longest.toString();
}
  
private void findPalindrome(String s, int lo, int hi, StringBuilder longest) {
  int n = s.length();
  StringBuilder sb = new StringBuilder();
  while (lo >= 0 && hi < n && s.charAt(lo) == s.charAt(hi)) {
    if (lo == hi) {
      sb.append(s.charAt(lo));
    } else {
      sb.insert(0, s.charAt(lo));
      sb.append(s.charAt(hi));
    }
    --lo;
    ++hi;
  }
  if (sb.length() > longest.length()) {
    longest.delete(0, longest.length());
    longest.append(sb);
  }
}

Time: $O(N^2)$
Space: $O(N)$

DP

Based on the brute-force solution, we can improve on it by avoiding unnecessary re-computation while validating palindromes. Consider the case ababa. If we already knew that bab is a palindrome, it is obvious that ababa must be a palindrome since the two end letters are the same.

So we can define dp[i][j] as true if the substring S(i, j) is a palindrome.

The recurrence is then obvious: dp[i][j] = (dp[i + 1][j - 1] && Si == Sj)

The base cases are: dp[i][i] = true, dp[i][i + 1] = (Si == Si+1).

Note: Determining ranges of i and j would be easy if you pick a starting point in the graph to get some intuition. For example, in this case j starts from i + 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public String longestPalindrome(String s) {
  if (s == null || s.length() == 0) {
    return "";
  }
  int n = s.length();
  boolean[][] dp = generateDP(s);
  // Check each substring
  int maxLen = 0;
  int[] maxIdx = new int[] { 0, 0 };
  for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) {
      if (dp[i][j] == true) {
        if (j - i + 1 > maxLen) {
          maxLen = j - i + 1;
          maxIdx[0] = i;
          maxIdx[1] = j;
        }
      }
    }
  }
  return s.substring(maxIdx[0], maxIdx[1] + 1);
}

private boolean[][] generateDP(String s) {
  int n = s.length();
  boolean[][] dp = new boolean[n][n];
  // Init
  for (int i = 0; i < n; ++i) { // diagonal
    dp[i][i] = true;
  }
  for (int i = 0; i < n - 1; ++i) { // one line below diagonal
    dp[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
  }
  // DP
  for (int i = n - 3; i >= 0; --i) {
    for (int j = i + 2; j < n; ++j) {
      dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
    }
  }
  return dp;
}

Time: $O(N^2)$
Space: $O(N^2)$