"Longest Palindromic Substring" challenge solution is inefficient

Question

I am trying to solve the Longest Palindromic Substring problem on LeetCode, and I have come up with a DP solution pasted below:

public class Solution {
    String      string;
    boolean[][] visited;
    String[][]  results;

    private boolean isPalindrome(String s){
        String test = new StringBuilder(s).reverse().toString();
        if(test.equals(s)) return true; else return false;
    }

    private String maxLengthString(String... args){
        String result = new String();
        for(String arg:args){
            if(arg.length() > result.length()) result = arg;
        }
        return result;
    }

    private String findLongestPalindrome(int start,int end){
        if(start >= end) return new String();
        else if(start >= string.length() || start < 0) return new String();
        else if(end <= 0 || end > string.length()) return new String();
        else{
            if(visited[start][end-1] == true) return results[start][end-1];
            String result = new String();
            if(this.isPalindrome(string.substring(start,end)))
                result = maxLengthString(string.substring(start,end),
                                        findLongestPalindrome(start+1,end),
                                        findLongestPalindrome(start,end-1));
            else result = maxLengthString(findLongestPalindrome(start+1,end),
                                          findLongestPalindrome(start,end-1));
            visited[start][end-1] = true;
            results[start][end-1] = result;
            return result;
        }
    }

    public String longestPalindrome(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function

        string = s;
        visited = new boolean[s.length()][s.length()];
        results = new String[s.length()][s.length()];

        return findLongestPalindrome(0,s.length());
    }
}

The algorithm is quite straightforward, but the online judge complains about it not being efficient enough. I am just wondering if this algorithm is slow by nature (in which case I have to find another algorithm) or if it's something about my implementation.

Answer 1

The proper way to solve it is to use a profiler to determine where the bottlenecks are, but by inspection, your search tree is at least twice the size it has to be and you will always expand the entire tree rather than terminating when you can.

if(this.isPalindrome(string.substring(start,end)))
            result = maxLengthString(string.substring(start,end),
                                    findLongestPalindrome(start+1,end),
                                    findLongestPalindrome(start,end-1));
        else result = maxLengthString(findLongestPalindrome(start+1,end),
                                      findLongestPalindrome(start,end-1));

if this.isPalindrome is true, then there is no way that findLongestPalindrome(start+1,end) or (start,end-1) could be longer. Rewriting this gives:

if(this.isPalindrome(sting.substring(start,end)))
    result = string.substring(start,end)
else
    ...

Answer 2

Why is it slow?

The input string S can be up to 1000 characters.

Your DP solution considers all \$\mathcal{O}(|S|^2)\$ substrings of S and you're checking for each of these substrings, if it is a palindrome, in linear time in terms of the length of this substring.

Faster solutions

You can do it easily in \$\mathcal{O}(|S|^2)\$ using a polynomial hashing technique.

There are of course more sophisticated and linear solutions based on the famous Manacher algorithm.