# Why does dp not work here? (Time Limit Exceed)

• public class Solution {
public String longestPalindrome(String s) {

``````    //check null
if(s == null){  return null; }

//check 0 or 1
int len = s.length();
if(len == 0 || len == 1){ return s; }

char[] array = s.toCharArray();
int start = 0, maxLen = 1;

// dp array to save distance from i to j
int dp[][] = new int[len][len];
for(int i = 0; i< len; i++){
// initialize array[i]
dp[i][i] = 1;
if(i < len - 1){
// initialize (array[i], array[i+1])
dp[i][i+1] = (array[i] == array[i+1]) ? 2 : -1;
if(dp[i][i+1] > maxLen){
start = i;
maxLen = dp[i][i+1];
}
}
}

int m = 0, n = 2;
while( m< len && n<len){
// if(previous dp isPalindrome and current char equals), return previous distance + 2
dp[m][n] = (dp[m+1][n-1] == -1 || array[m] != array[n] ) ? -1 : (dp[m+1][n-1] + 2);
if(maxLen < dp[m][n]){
start = m;
maxLen = dp[m][n];
}
m++;
n++;
if(n == len){
n = len - m + 1;
m = 0;
}
}

return s.substring(start, start+maxLen);

}
``````

}

• Have you figured it out?

I also use the DP here which is O(n^2). But it TLE at "aaaaa..." test case. Don't know why.

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