**QUESTION**

We are given two sequences and we have to find the longest subsequence present in both of them. The subsequence must appear in the same order in both the sequences and need not be continuous.\n\nFor example:\n\nS1 = \”AABCEGACA\” \nS2 = \”ABCFGCBAHKA\”\n\nLength of the Longest Common Subsequence of S1 and S2 is 6. \n\”ABCGCA\” is the LCS of S1 and S2.\n\nLCS isn’t necessarily unique, there can be more than one common subsequence with the maximum length.\n\nFor example:\n\nS1 = \”AABBCC\” S2 = \”ABCAB\”\n\nThe length of the LCS is 3.\n\nThe LCS can be \”ABC\”, \”AAB\” or \”ABB\”.

**ANSWER**

```
import java.io.*;
import java.util.*;
public class TestClass {
static void lcs(String X, String Y, int m, int n)
{
int[][] L = new int[m+1][n+1];
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X.charAt(i-1) == Y.charAt(j-1))
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = Math.max(L[i-1][j], L[i][j-1]);
}
}
int index = L[m][n];
int temp = index;
char[] lcs = new char[index+1];
lcs[index] = '\0';
int i = m, j = n;
while (i > 0 && j > 0)
{
if (X.charAt(i-1) == Y.charAt(j-1))
{
lcs[index-1] = X.charAt(i-1);
i--;
j--;
index--;
}
else if (L[i-1][j] > L[i][j-1])
i--;
else
j--;
}
System.out.print("The Longest Common Subsequence is ");
for(int k=0;k<=temp;k++)
System.out.print(lcs[k]);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String X;
String Y;
Y= scan.nextLine();
X = scan.nextLine();
int m = X.length();
int n = Y.length();
lcs(X, Y, m, n);
}
}
```