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