   Type like pro

# 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);
}
}
```