## Virtusa Polaris – Fresher Interview Questions with answers

### LONGEST COMMON SEQUENCE

Virtusa Core COE Version 1

Given two strings, ‘x’ and ‘y’ (1 <= lenth(x), length(y) <= 1000), find the length of their Longest Common Subsequence (LCS). The strings contains only lowercase letters.

You need to fill in a function that takes input two strings and sets the output variable to the length of their LCS.

Input

inputl the string ‘x’

input2: the string ‘y’

Output

Return the length of the LCS of ‘x’ and ‘y’

________________________________________________________________

/* A Naive recursive implementation of LCS problem in java*/

public class LongestCommonSubsequence

{

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */

int lcs( char[] X, char[] Y, int m, int n )

{

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

return 0;

if (X[m-1] == Y[n-1])

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

else

return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));

}

/* Utility function to get max of 2 integers */

int max(int a, int b)

{

return (a > b)? a : b;

}

public static void main(String[] args)

{

LongestCommonSubsequence lcs = new LongestCommonSubsequence();

String s1 = “aba”;

String s2 = “ababa”;

char[] X=s1.toCharArray();

char[] Y=s2.toCharArray();

int m = X.length;

int n = Y.length;

System.out.println(“Length of LCS is” + ” ” +

lcs.lcs( X, Y, m, n ) );

}

}

_________________________________________________________________

### LCS Problem Statement:

2 ) Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

Here is the source code of the Java Program to implement Longest Common Substring Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

1. /**

2. ** Java Program to implement Longest Common Substring Algorithm

3.  **/

4.

7. import java.io.IOException;

8.

9. /** Class  LongestCommonSubstring **/

10.          public class  LongestCommonSubstring

11.          {

12.              /** function lcs **/

13.              public String lcs(String str1, String str2)

14.              {

15.                  int l1 = str1.length();

16.                  int l2 = str2.length();

17.

18.                  int[][] arr = new int[l1 + 1][l2 + 1];

19.                  int len = 0, pos = -1;

20.

21.                  for (int x = 1; x < l1 + 1; x++)

22.                  {

23.                      for (int y = 1; y < l2 + 1; y++)

24.                      {

25.                          if (str1.charAt(x – 1) == str2.charAt(y – 1))

26.                          {

27.                                  arr[x][y] = arr[x – 1][y – 1] + 1;

28.                                  if (arr[x][y] > len)

29.                                  {

30.                                      len = arr[x][y];

31.                                      pos = x;

32.                                  }

33.                          }

34.                          else

35.                              arr[x][y] = 0;

36.                      }

37.                  }

38.

39.                  return str1.substring(pos – len, pos);

40.              }

41.

42.              /** Main Function **/

43.              public static void main(String[] args) throws IOException

44.              {

46.                  System.out.println(“Longest Common Substring Algorithm Test\n”);

47.

48.                  System.out.println(“\nEnter string 1”);

49.                  String str1 = br.readLine();

50.

51.                  System.out.println(“\nEnter string 2”);

52.                  String str2 = br.readLine();

53.

54.                  LongestCommonSubstring obj = new LongestCommonSubstring();

55.                  String result = obj.lcs(str1, str2);

56.

57.                  System.out.println(“\nLongest Common Substring : “+ result);

58.              }

59.          }

_______________________________________________________________________

COURTESY  :

https://www.sanfoundry.com/java-program-longest-common-substring-algorithm/

https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

https://www.sanfoundry.com/java-program-generate-all-possible-combinations-given-list-numbers/

https://www.geeksforgeeks.org/printing-longest-common-subsequence/