package com.imaginea.dynamicprogramming;
import java.util.HashMap;
import java.util.Map;
/*
* Dynamic Programming implementation to get longest Palindrome in string sequence
* In order to solve a given problem, using a dynamic programming approach, we need to solve different parts of the problem (subproblems),
* then combine the solutions of the subproblems to reach an overall solution
* It is applicable to problems exhibiting the properties of 1. Optimal Substructure and 2. Overlapping Subproblem
* 1. Optimal Substructure: If optimal solution can be constructed efficiently from optimal solution of its subproblem.
* 2. Overlapping Subproblem: if the problem can be broken down into subproblem which are reused several times rather than to generate new subproblem.
*
* LP(i,j) =1 if i==j
* =1 if j=i+1 and x[i]!=x[j]
* =2 if j=i+1 and x[i]==x[j]
* =LP(i+1, j-1)+2
* =max(LP(i+1,j),LP(i,j-1))
*/
public class LongestPalindromeSequence {
static Map<String, Integer> computedValues = new HashMap<String, Integer>();
public static void main(String[] args) {
int length = LP("BBABCBCAB");
System.out.println("Paliandrome Length::"+length);
}
private static int LP(String str){
if(computedValues.get(str)!= null){
return computedValues.get(str);
}
if(str.length()>0){
int i=0;
int j=str.length()-1;
if(i==j){
return 1;
}else if(j == (i+1)){
if(str.charAt(i)==str.charAt(j)){
return 2;
}else{
return 1;
}
}else if(str.charAt(i)==str.charAt(j)){
int result = LP(str.substring(i+1, j))+2;
computedValues.put(str,result);
return result;
}else{
int result = max(LP(str.substring(i+1, j+1)),LP(str.substring(i, j)));
computedValues.put(str, result);
return result;
}
}else{
System.out.println("Invalid String");
return -1;
}
}
private static int max(int n, int m){
if(n>m)
return n;
else
return m;
}
}