Longest Common Subsequence

In this article we will find the longest increasing subsequence between two given strings. Suppose we have two strings, S1 and S2, such that:

S1= “akfdcmejf”
S2=”sfkpdcnmej”

The Longest Common Subsequence (LCS) between these two strings is “kdcmej”. Just because it’s a subsequence doesn’t necessarily mean that it will be contigous.

There are different methods to compute this. First we will try naive methods and then an efficient solution for finding the length of the LCS.

Naive Method

In this method we will traverse both the strings and for each character in string S2 we will traverse string S1 again and again. That means if we find a condition where both the characters in S1 and S2 are the same then we will update the count and then we won’t check further for the same character in S1.

Algorithm

Step1: Input two strings from user, initialize count=0

Step2: Loop1
To traverse S2, initialize char c2=S2[currentIndexi - 1]

Step3: Loop 2
To traverse S1 over S2, initialize char c1=S1[currenIndexJ - 1]

Step4: check for both characters

If (c1 is equal to c2)
Update count; break from inner loop;
Else
Traverse for next character in S1, jj++

Step5: updated count will be the length of LCS

Complexity Analysis: O(N²)

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class MyClass {

  public static int LCSBrute(String S1, String S2) {

    int ccount = 0;

    for (int ii = 0; ii < S1.length(); ii++) {
      for (int jj = 0; jj < S2.length(); jj++) {

        if (S1.charAt(ii) == S2.charAt(jj)) {
          ccount++;
          break;
        }
      }

    }
    return ccount;
  }
  public static void main(String args[]) {

    String S1 = "akfdcmejf";
    String S2 = "sfkpdcnmej";

    System.out.println("Length of LongestCommonSubSequence:" + LCSBrute(S1, S2));

  }

}

Code Snippet

Memoize - Efficient Approach

In this approach we will use the already completed calculations and store them in a matrix so that we don’t have to calculate them again. That means we will memoize already calculated results which will make our program efficient for calculating the LCS.

To calculate LCS in the memoize technique we first form a matrix with rows as characters of S1 and columns as characters of the S2 string. Then for each cell we will calculate the value of the cell. The value of each cell says that from the current index of string (current i^th index of cell) of S1 to the current index (current j^th index of cell) of string S2 there exists a subsequence of length L_i where L_i is the value of the current cell.

Algorithm

Step1: Input String S1, S2,

Initialize i , j where Length of S1 , S2 → l1, l2
Take matrix memoize[l1][l2], initialize first row and column with 0
For taken strings after the first step we will have a matrix like:

Step2: current i=0 and j=0
if(S1[0]==S2[0]) set memoize[0][0] with 0 else 1

Step3: Loop for traversing rows of matrix

Step4: Inner loop for traversing columns

Step5: if for any cell S1[i]==S2[j]
Then update memoize[ i ][ j ] with memoize[ i-1 ][ j-1 ] + 1

Else:

Then update memoize[ i ][ j ] with Max(memoize[ i-1 ][ j ], memoize[ i ][ j-1 ])

Step6: Once we come out of a loop our matrix will be updated as such

Complexity:

Space Complexity: L1*L2
Time Complexity: O(L1*L2), where L1,L2 are the length of strings.

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class MyClass {

  public static int MemoizeDP(String S1, String S2) {
    int ll1 = S1.length();
    int ll2 = S2.length();

    //int ccount=0;
    int memoize[][] = new int[ll1 + 1][ll2 + 1];

    for (int ii = 0; ii <= ll1; ii++) {

      for (int jj = 0; jj <= ll2; jj++) {
        if (ii == 0 || jj == 0)
          memoize[ii][jj] = 0;
        else if (S1.charAt(ii - 1) == S2.charAt(jj - 1))
          memoize[ii][jj] = memoize[ii - 1][jj - 1] + 1;
        else
          memoize[ii][jj] = Math.max(memoize[ii - 1][jj], memoize[ii][jj - 1]);
      }
    }
    return memoize[ll1][ll2];

  }

  public static void main(String args[]) {

    String S1 = "akfdcmejf";
    String S2 = "sfkpdcnmej";

    System.out.println("Length of LongestCommonSubSequence:" + MemoizeDP(S1, S2));
  }
}

Code Snippet

References

https://webhome.cs.uvic.ca/~thomo/papers/bibe07.pdf
https://www-igm.univ-mlv.fr/~lecroq/seqcomp/node4.html
https://courses.engr.illinois.edu/cs374/fa2020/lec_prerec/14/14_2_6_0.pdf