# Java DP solution with optimization in space from O(n^2) to O(n), time O(n^2) with very clear explanations

• The original DP solution: time O(n^2), space O(n^2)

• The outer for-loop's index i goes from n-1 to 0, and the inner for-loop's index j goes from i to n-1, the making i occurs before j, thus we use `dp[i][j]` to represent if the substring `s(i,j)` is a palindrome.
• to check if substring `s(i,j)` is a palindrome, we first make sure the two characters at `s(i)` and `s(j)` equal, then there are two cases to consider:
• if `j - i < 3`, which means that the substring's length is less than 3 (e.g. "aba", "ab", "a"), then `s(i,j)` is a palindrome.
• if the "inner" substring `s(i+1, j-1)`, without the two characters at `s(i)` and `s(j)` is a palindrome, or `dp[i+1][j-1]`, then `s(i,j)` is a palindrome.
• when j = 0, j - i is always less than 3, so we never have an index out of bound exception for `dp[i+1][j-1]`
• Then we check if `dp[i][j]` is true, or if `s(i,j)` is a palindrome, and compare its length with the length of the temporary result, and update the result with the longer one.
``````public String longestPalindrome(String s) {
int n = s.length();
String result = "";
boolean[][] dp = new boolean[n][n];

// i goes from n - 1 to 0, j goes from i to n - 1, to make sure i occurs before j
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i+1][j-1]);
// if dp[i][j] is true，update result
if(dp[i][j] && (result.equals("") || j - i + 1 > result.length())) {
result = s.substring(i, j+1); // j+1 not j, since substring includes j
}
}
}
return result;
}
``````

My thoughs on optimization of space complexity:

We only use `dp[i+1][j-1]` to update `dp[i][j]`. We could try reducing the 2D array to 1D array.
Since the outer for loop is `for (int i = n - 1; i >= 0; i--)` (the index i has a decreasing order), we could notice that we only need to maintain a 1D array for index j, or using `dp[j-1]` to update dp[j]. To do so, we need the inner for loop's index j to also go backward from n-1 to i. In this way, when we use `dp[j-1]` to update `dp[j]`, `dp[j-1]` is actually the same as 2D array's `dp[i+1][j-1]`, where i+1 is from the last for loop. The reason for index j's decreasing order is to make sure we do not modify the value of `dp[j-1]` before we use `dp[j-1]` to update `dp[j]`.

The optimized DP solution: time O(n^2), space O(n)

``````public static String longestPalindrome(String s) {
int n = s.length();
String result = "";
boolean[] dp = new boolean[n];

for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= i; j--) { // decreasing order
// dp[j-1] is the same as dp[i+1][i-1]
// since both dp[j-1] and dp[i+1][j-1] are from the last iteration of the outer loop
dp[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[j-1]);
if(dp[j] && (result.equals("") || j - i + 1 > result.length())) {
result = s.substring(i, j+1);
}
}
}
return result;
}
``````

• Nice Solution. Easy to understand.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.