Longest palindrome dynamic

Problem

Given a string find the longest possible substring which is a palindrome.

Solution

We will use dynamic programming to solve this problem. Given a substring if the first and last character are not same then it is not a palindrome, but if the end characters are same then the solution depends upon the inner string. So this is a subproblem, to find out whether the inner string is a palindrome or not. This subproblem may need to be solved several times. So for this we store the result of once computed substring in a two dimensional array, where array[i][j]=true off substring(i,j) is a palindrome. So the base cases are arr[i][i]=true, arr[i][i+1]=true if character at i and i+1 is same. For other cases arr[i][j]=arr[i-1][j-1] AND (charAt(i)==charAt(j)). While computing the two dimensional array we keep track of highest found length and startIndex. The complexity of this solution is O(n^2) because we will fill each of the cells of 2 d array only once.

Code

public class LargestPalindromeRecursive
{
 public static void main(String[] args)
 {
  String str = "acbcaccccaccc";
  String result = findLargestPalindrome(str);
  System.out.println(result);
 }

 private static String findLargestPalindrome(String str)
 {
  if(str==null ||str.length()==0)
   return "";
  boolean[][] memo = new boolean[str.length()][str.length()];
  int maxStart = 0;
  int maxLength = 1;
  for (int startIndex = 0; startIndex < str.length(); 
   ++startIndex)
  {
   memo[startIndex][startIndex] = true;
  }
  for (int startIndex = 0; startIndex < str.length() - 1; 
    ++startIndex)
  {
   if (str.charAt(startIndex) == str.charAt(startIndex + 1))
   {
    memo[startIndex][startIndex + 1] = true;
    maxStart = startIndex;
    maxLength = 2;
   }
  }
  for (int length = 3; length <= str.length(); ++length)
  {
   for (int startIndex = 0; startIndex < str.length() - 
    length + 1; ++startIndex)
   {
    int endIndex = startIndex + length - 1;
    if (str.charAt(startIndex) == str.charAt(endIndex)
      && memo[startIndex + 1][endIndex - 1] == true)
    {
     memo[startIndex][endIndex] = true;
     maxStart = startIndex;
     maxLength = length;
    }

   }
  }
  return str.substring(maxStart, maxStart + maxLength);
 }
}