public class LongestComonSubsequance {
public static void main(String[] args) {
String str = "ABCDXYS";
String st = "ABXY";
System.out.println(getSubseqaunce(str, st));
}
private static String getSubseqaunce(String str, String st) {
int[][] arr = new int[st.length()+1][str.length()+1];
for(int i=1;i<=st.length();i++){
for(int j=1;j<=str.length();j++){
if(st.charAt(i-1) == str.charAt(j-1)){
arr[i][j] = arr[i-1][j-1]+1;
}else{
arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);
}
}
}
for(int[] i: arr){
System.out.println(Arrays.toString(i));
}
int length = arr[st.length()][str.length()];
System.out.println(length);
String result = getSubSequance(str, st, str.length(), st.length(), arr);
return result;
}
private static String getSubSequance(String str, String st, int col, int row, int[][] arr) {
if(row == 0 || col == 0)return "";
if(str.charAt(col-1) == st.charAt(row-1)){
return getSubSequance(str, st, col-1,row-1, arr)+str.charAt(col-1);
}
if(arr[row][col-1]>arr[row-1][col]){
return getSubSequance(str, st,col-1, row, arr);
}
return getSubSequance(str, st, col, row-1, arr);
}
}