Time Limit Exceeded for Longest Palindromic Substring

• It would be very helpful if anybody can point out the bug here.

package longestPalindromicSubstr;

public class Solution {
private int table [] [];
private int len;
private static final int NOT_COMPUTED = -1;
private static final int NOT_PALINDROME = 0;

``````public String longestPalindrome(String s) {
int i = 0, j = 0;
len = s.length();
table = new int [s.length()][s.length()];

for(i=0; i< len; i++) {
for(j = 0; j < len; j++) {
table[i][j] = NOT_COMPUTED;
}
}

//First fill the diagonals and adjacent to diagonals
for(i = 0; i < s.length(); i++) {
table[i][i] = 1;
if(i+1 < len) {
if(s.charAt(i) == s.charAt(i+1)) {
table[i][i+1] = 2;
}else {
table[i][i+1] = NOT_PALINDROME;
}
}
}

//Now fill other rows
for(i = 0; i < len; i++) {
for(j = 0; j < len; j++) {
if(j <= i+1)
continue;
if(s.charAt(i) == s.charAt(j) && table[i][j] == NOT_COMPUTED) {
compute(i, j);
}
}
}

return findLongestSubstr(s);
}

private void compute(int row, int col) {
if(col < row) {
System.out.println("Should not reach here");
System.exit(-1);
}

if(table[row+1][col-1] == NOT_COMPUTED)
compute(row+1, col-1);

if(table[row+1][col-1] == NOT_PALINDROME)
table[row][col] = NOT_PALINDROME;
else
table[row][col] = table[row+1][col-1] + 2;
}

private String findLongestSubstr(String s) {
int currMax = 0;
int maxRow = 0;
int maxCol = 0;

for(int i = 0; i < len ; i++) {
for(int j = 0; j < len; j++) {
if(j < i)
continue;
if(table[i][j] > currMax) {
currMax = table[i][j];
maxRow = i;
maxCol = j;
}
}
}

return s.substring(maxRow, maxCol+1);
}
``````

}

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