Java Dynamic Programming Solution - 8ms Worst case, but getting TLE

• My idea is s[n] will know the longest palindrome in 0...n substring. When we move to i, it must create a larger palindrome than s[i -1] knows of for it to be considered. To check that we start looking for ith character from start. When we find one (lets say at m index), we check if m...i is a palindrome. If not, we keep looking til the length becomes smaller than what s[i - 1] knows of. If none found, then we carry forward the same palindrome that s[i - 1] to s[i];

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

String[] s = new String[input.length()];
int longestPalindromeLength;
s[0] = input.substring(0, 1);
//System.out.println("s[0]: " + s[0]);
int j;
for (int i = 1; i < input.length(); i++) {
longestPalindromeLength = s[i - 1].length();
j = 0;
while (j <= i - longestPalindromeLength) {
if (input.charAt(i) == input.charAt(j)) {
//System.out.println("checking palindrome from " + j + " - " + (i + 1) + ": " + input.substring(j, i + 1));
if (isPalindrome(input.substring(j, i + 1))) {
//System.out.println("found palindrome from " + j + " - " + (i + 1) + ": " + input.substring(j, i + 1));
s[i] = input.substring(j, i + 1);
break;
}
}

j++;
}

if (s[i] == null) {
s[i] = s[i - 1];
}

//System.out.println("s[" + i + "]: " + s[i]);
}

return s[input.length() - 1];
}

private boolean isPalindrome(String input) {
if ((input == null) || (input.length() <= 1)) {
return true;
}

int size = input.length();
for (int i = 0; i <= size / 2; i++) {
if (input.charAt(i) != input.charAt(size - i - 1)) {
return false;
}
}

return true;
}``````

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