"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.

• But I'm Not A Wrapper Class: Also, it's probably slow because of the recursion.
• bblincoe: I see you are using a recursive approach. Have you tried to create an iterative solution and compare the results?
• Boyu Fang: @bblincoe I will try later
• Dukeling: @Bohemian I'd imagine, to become efficient enough, it would require a fundamentally different approach, i.e. basically a complete rewrite. Wouldn't this be beyond the scope of Code Review? UPDATE - Well, the question doesn't actually seem to be asking about a different approach, just why it's slow, so it may be fine for there, I'm not sure.

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
 ...

• pkacprzak: In the worst case it doesn't help at all

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.