# Share my Java solution using dynamic programming

• `dp(i, j)` represents whether `s(i ... j)` can form a palindromic substring, `dp(i, j)` is true when `s(i)` equals to `s(j)` and `s(i+1 ... j-1)` is a palindromic substring. When we found a palindrome, check if it's the longest one. Time complexity O(n^2).

``````public String longestPalindrome(String s) {
int n = s.length();
String res = null;

boolean[][] dp = new boolean[n][n];

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] && (res == null || j - i + 1 > res.length())) {
res = s.substring(i, j + 1);
}
}
}

return res;
}``````

• if the string is too large,your method will limited with time

• Hi @jeantimex, how does it compare to the other O(n^2) solutions? I think they are doing the same thing with the left and right pointers. dp(i, j) can have only one center and they are directly expanding from there.

• A little improvement: don't substring in for j loop. Do that after for j loop finishes.

``````public String longestPalindrome(String s) {
if(s==null || s.length() <= 1) return s;

boolean[][] dp = new boolean[s.length()][s.length()];
char[] w = s.toCharArray();
int maxLen = 0;
String maxSub = null;

dp[s.length()-1][s.length()-1] = true;
for(int i = s.length()-2;i>=0;--i){ //试每一个起点
int maxJ = i;
for (int j = i+1; j < s.length(); j++) { //每一个终点
if(w[j] == w[i] && (j<i+3 || dp[i+1][j-1])){
dp[i][j] = true;
maxJ = j;
}else{
dp[i][j] = false; //不是立即返回.
}
}

if(maxJ - i+1 > maxLen){
maxLen = maxJ - i+1;
maxSub = s.substring(i,maxJ+1);
}
}
return maxSub;
}``````

• It‘s easy to understand

• I'm using the exactly same method, except I'm traversing from front, but it does work. Does it mean that it only works from back? Someone heeeeelp!

Input:
"abb"
Output:
"abb"
Expected:
"bb"

``````public class Solution {
public String longestPalindrome(String s) {
s = s.trim();
if ( s == null || s.length() == 0 ) {return "";}
String result = "";
boolean[][] map = new boolean[s.length()][s.length()];
char[] string_char = s.toCharArray();
for ( int i = 0; i < s.length(); ++i ) {
for ( int j = i; j >= 0; --j ) {
map[j][i] = (string_char[i] == string_char[j] && (( i - j) < 3 || map[j+1][i-1]) );
if (( i - j + 1 ) > result.length() ) {
result = s.substring(j, i+1);
}
}
}
return result;
}
}
``````

• @Juan55555 Hope my code helps you.

``````    public String longestPalindrome(String s) {
if(s==null || s.length()<=1) return s;
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i=0; i<s.length(); i++) {
dp[i][i] = true;
if(i<s.length()-1 && s.charAt(i)==s.charAt(i+1)){
dp[i][i+1] = true;
}
}
String ret = "";
for(int i=1; i<s.length(); i++){
for(int j=i-1; j>=0; j--){
dp[j][i] = (s.charAt(i) == s.charAt(j)) && (i-j<3 || dp[j+1][i-1]);
// System.out.println(ret);
if(dp[j][i] && (i-j+1)>ret.length()){
ret = s.substring(j, i+1);
}
}
}
return ret;
}
``````

• @Juan55555 you missed one condition at the result-update line, which should be

if ( map[j][i] && ( i - j + 1 ) > result.length() )

• Thanks guys!!

• Although the time complexity and space complexity are both O(n^2), which is not as optimized as other solutions, I'm very happy to read this solution. This is the first time I see "2-d dynamic programming". Very interesting!

• Could someone explain to me why the first for loop starts from the end of the string, instead of starts from 0?

• This post is deleted!

• My take:

public String longestPalindrome(String s) {
int [][] dp = new int [s.length() + 1][s.length() + 1];

``````	int maxLength = 0;

for (int row = 0; row < s.length(); row ++) {

for (int col = row; col >= 0; col --) {
if (s.charAt(row) == s.charAt(col))
dp [row + 1][col + 1] = (row == col) ? 1 : (row - col == 1 || dp [row][col + 2] > 0) ? dp [row][col + 2] + 2 : 0;

if (dp [row + 1][col + 1] > maxLength) {
maxLength = Math.max (maxLength, dp [row + 1][col + 1]);
answer = s.substring(col, row + 1);
}
}
}

}``````

• Thanks @jeantimex for this beautiful solution and explanation. Here is the same code with useful comments which helped me understand

``````public class Solution {
public static String longestPalindrome(String s) {
int n = s.length();
String res = null;
int palindromeStartsAt = 0, maxLen = 0;

boolean[][] dp = new boolean[n][n];
// dp[i][j] indicates whether substring s starting at index i and ending at j is palindrome

for(int i = n-1; i >= 0; i--) { // keep increasing the possible palindrome string
for(int j = i; j < n; j++) { // find the max palindrome within this window of (i,j)

//check if substring between (i,j) is palindrome
dp[i][j] = (s.charAt(i) == s.charAt(j)) // chars at i and j should match
&&
( j-i < 3  // if window is less than or equal to 3, just end chars should match
|| dp[i+1][j-1]  ); // if window is > 3, substring (i+1, j-1) should be palindrome too

//update max palindrome string
if(dp[i][j] && (j-i+1 > maxLen)) {
palindromeStartsAt = i;
maxLen = j-i+1;
}
}
}
return s.substring(palindromeStartsAt, palindromeStartsAt+maxLen);
}
}
``````

• @sleeter
Thanks for your comment, but I still can not understand the condition `j - i < 3`, what does the window size of 3 means?

• @wangchaogo1990 HI, `j - i < 3` condiiton is important because some (i, j) pair would not appear in main loop. Suppose `j = i + 1` and you leave `j - i < 3` condition out, then you need to evaluate `dp[i+1, j-1]` while it would not be correct due to `i+1 > j-1`.

• @Vandermode
Thanks for your explanation, it gives me an insight.
Cause the algorithm calculates the right triangle, if we want `dp[i + 1][j - 1]` works, need `i + 1 <= j - 1`, meaning `j - i >= 2`, so those `i,j` pairs which are not shown in the main loop are `j - i < 2`, I think this is enough.

• @Evelyninjuly cause the dp[i][j] is derived from the dp[i + 1][j - 1] as for i we must know i + 1 so the first loop must come from the end of the string