Print LCS Dynamic programming

#1

import java.util.*;

public class Main {

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String s1 = sc.next();
	String s2 = sc.next();
	LCS(s1,s2);
}

public static void  LCS(String str1,String str2) {
	    int[][] strg= new int[str1.length()+1][str2.length()+1];
	//seed
			strg[str1.length()][str2.length()] = 0;
			
			for(int i=str1.length();i>=0;i--) {
				for(int j=str2.length();j>=0;j--) {
					if(i == str1.length() || j==str2.length()) {
						strg[i][j] = 0;
						continue;
					}
					
					if(str1.charAt(i) == str2.charAt(j)) {
						strg[i][j] = strg[i+1][j+1] + 1;
					}else {
						strg[i][j] = Math.max(strg[i+1][j], strg[i][j+1]);
					}
				}
			}
			
			int index = strg[0][0];
			int temp = index;
			
			char[] lcs = new char[index];
			
			
			
			int i=0,j=0;
			while(i<str1.length() && j<str2.length()) {
				if(str1.charAt(i) == str2.charAt(j)) {
					
					lcs[index-1] = str1.charAt(i); 
					i++;
					j++;
					index--;
				}else if(strg[i+1][j] > strg[i][j+1]) {
					i++;
				}else {
					j++;
				}
			}
			
				Arrays.sort(lcs);
			for(int k=0;k<temp;k++) {
				System.out.print(lcs[k]);
			}
			
			
			

}

}

//Im not passing on of the test cases is there something wrong in the code

#2

@Siddharth_sharma1808,

  1. Construct dp[m+1][n+1] using the count LCS dynamic programming solution.

  2. The value dp[m][n] contains length of LCS. Create a character array lcs[] of length equal to the length of lcs plus 1 (one extra to store \0).

  3. Traverse the 2D array starting from dp[m][n]. Do following for every cell dp[i][j]

  • If characters (in X and Y) corresponding to dp[i][j] are same (Or X[i-1] == Y[j-1]), then include this character as part of LCS.
  • Else compare values of dp[i-1][j] and dp[i][j-1] and go in direction of greater value.
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.