Question

Given two strings, 'x' and 'y' (1 <= length(x), length(y) <= 1000), find the length of their Longest Common subsequence (LCS). The strings contains only lowercase letters. Write a program that takes in two string inputs and returns the length of their LCS. Input Specification: input1: input string 'x' input2: input string 'y' Output Specification: Return the length of the LCS of 'x' and 'y'. Example 1: input1: aba input2: ababa Output: 3 Explanation: Length of Longest common subsequence is 3 that is "aba".

Answer 1

Answer:

1000 *2 = 2000

Glt bhi ho skta hai ye

Answer 2

input1: aba

input2: ababa

Output: 3

The Length of the Longest common subsequence is 3 that is "aba".

Explanation:

class Main

{

   

   public static int LCSLength(String X, String Y, int m, int n)

   {

       

       if (m == 0 || n == 0)

{

           return 0;

       }

 

       

       if (X.charAt(m - 1) == Y.charAt(n - 1)) {

           return LCSLength(X, Y, m - 1, n - 1) + 1;

       }

 

       

       return Integer.max(LCSLength(X, Y, m, n - 1),

                       LCSLength(X, Y, m - 1, n));

   }

 

   public static void main(String[] args)

   {

       String X = "ABCBDAB", Y = "BDCABA";

 

       System.out.println("The length of the LCS is "

               + LCSLength(X, Y, X.length(), Y.length()));

   }

}