Clean Java solution using DP, yet the time complexity is O(N^2)

• ``````public class Solution {
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) {
return "";
}
int len = s.length();
boolean[][] dp = new boolean[len][len];
int start = 0;
int end = 0;
int max = 0;
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j <= i; j++) {
if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
dp[j][i] = true;
}
if(dp[j][i] && max < i - j + 1) {
max = i - j + 1;
start = j;
end = i;
}
}
}
return s.substring(start, end + 1);
}
}``````

• `DP C++ version`

``````string longestPalindrome(string s) {

int n = (int)s.length();

int dp[n][n];

int l = 0, r = 0, maxx = 1;

for(int i = 0; i<n; i++)
for(int j = 0; j<n; j++)
dp[i][j] = (i == j) ? 1 : 0;

for(int len = 1; len<n; len++) {
for(int i = 0; i<n-len; i++) {
int j = i+len;
if(s[i] == s[j] && dp[i+1][j-1] == j-i-1) {
dp[i][j] = dp[i+1][j-1] + 2;
if(dp[i][j] > maxx) {
maxx = dp[i][j];
l = i;
r = j;
}
} else
dp[i][j] = 0;
}
}

return s.substr(l, maxx);
}
``````

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