DNA to Code: Mastering the Longest Common Subsequence Algorithm.

Before we solve this problem let's understand why this algorithm i.e longest common subsequence is important?

To address Longest Common Subsequence i will use LCS interchangeably.

Let's take an example of DNA:

We have two DNA sequences,

1. one from a human
2. one from a chimpanzee.

The LCS function calculates the length of the longest common subsequence between these two DNA sequences.

const humanDNA = "ATGCGATCGTAGCTAGCTAGCTGATCG";

const chimpanzeeDNA = "ATGCGATCGTAGCTAGCTAGCTGATCGATCG"

Running LCS algorithm on DNAs data give us following result:

DNA Sequence Comparison Result: {
 lcsLength: 27,
 similarity: '87.10%',
 sequence1Length: 27,
 sequence2Length: 31
}

In practice, this algorithm could be used in other areas such as:

1. Version Control Systems:
2. Git and other version control systems use LCS-like algorithms to show differences between versions of files.
3. Plagiarism Detection:
4. LCS can be used to compare documents and identify potential instances of plagiarism by finding common sequences of words or phrases.
5. Spell Checking and Autocorrect:
6. LCS can help in suggesting corrections for misspelled words by finding the closest match in a dictionary.

This is an example of why learning LCS is important.

Now that we understand why we need to understand this algorithm, let's see how we can solve this question?

Question:

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

The comparison table:

"abcde"
     "ace"


     ace
     return 3


                    "abcde" "ace"
                        |
                    1+ bcde ce      since b and c are not equal
                   /              1 \
             cde   ce                bcde e
             /                        /      \
          1 + de e                cde e     bcde ''
          /                      1   / \             0
       e  e                    de e   cde
        /                        / \       0
      1                      e e   de ''
                            1     0




Another visual representation of comparison:



                    ('abcde', 'ace')
                    ______|______
                   |            |
          ('bcde', 'ce')   ('abcde', 'ce')
             ______|______         |
            |            |        |
       ('cde', 'ce')   ('bcde', 'e')  ('bcde', '')
          ______|______   |
         |            |  |
    ('de', 'e')   ('cde', '')  ('cde', '')
         |            |
    ('e', 'e')    ('de', '')
         |
    ('', '')

another comaparison:

var longestCommonSubsequence = function(text1, text2) {
    return lcs(0, 0, text1, text2)
};

function lcs(i , j, A, B){
   // base case
   if( A[i] === undefined || B[j] === undefined){
        return 0
   }
    if(A[i] === B[j]){
        return 1 + lcs(i + 1, j + 1, A, B)
    }else{
        return Math.max(
            lcs(i + 1, j , A, B) ,
             lcs(i , j+ 1, A, B)
         )
    }         
 }

if we submit the code to leetcode, it might take alot of time to calculate for long strings.

As seen in the image below. For each leaf of the tree node, even though the values are same, we will recompute it for all, eventually taking more time. If we have a limit, we will get following error.

Above code is brute force way of calculating each branch of the tree, even though we have calculated before. To optimise any dynamic programming problem we use memoization technique.

LCS DP Table Filling Example:

Dp is short form of dynamic programming.

Let's use an array i.e [2 *2] dp.

1. Text1 (rows) = 'acdf'
2. Text2 (columns) = 'abcd'

Technique: We're using a 2D array to store the length of the LCS for each combination of prefixes of the two strings. We fill this table iteratively.

Step-by-step process:

1. Initialize the table with 0s:

Copy
    a  b  c  d
  0 0  0  0  0
a 0
c 0
d 0
f 0

1. Fill row by row, column by column:

• If characters match, take diagonal value + 1
• If not, take max of left and top value

1. After filling 'a' row:

Copy
    a  b  c  d
  0 0  0  0  0
a 1  1  1  1
c 0
d 0
f 0

1. After filling 'c' row:

Copy
    a  b  c  d
  0 0  0  0  0
a 1  1  1  1
c 1  1  2  2
d 0
f 0

1. After filling 'd' row:

Copy
    a  b  c  d
  0 0  0  0  0
a 1  1  1  1
c 1  1  2  2
d 1  1  2  3
f 0

1. Final table after filling 'f' row:

Copy
    a  b  c  d
  0 0  0  0  0
a 1  1  1  1
c 1  1  2  2
d 1  1  2  3
f 1  1  2  3

The bottom-right cell (3) gives the length of the LCS. The LCS is "acd".

thus this can be written as:

var longestCommonSubsequence = function(text1, text2) {
    const dp = new Array(text1.length).fill(0).map(o => new Array(text2.length).fill(undefined))
    return lcsOptimized(0, 0, text1, text2, dp)
};


function lcsOptimized(i, j, A, B, dp){
   if (i === A.length || j === B.length) {
        return 0;
    }
    // If we've already computed this subproblem, return the cached result
    if (dp[i][j] !== undefined) {
        return dp[i][j];
    }
    if(A[i] === B[j]){
        dp[i][j] =  1 + lcsOptimized(i + 1, j + 1, A, B, dp)
    }else{
        dp[i][j] = Math.max(
            lcsOptimized(i + 1, j , A, B, dp),
            lcsOptimized(i, j + 1, A , B, dp)
        )
    }
    return dp[i][j]
}

Complexities:

Time Complexity: O(N * M)

• N is the length of text1
• M is the length of text2
• In the worst case, we might need to fill out the entire dp array, which has N * M elements
• Each cell is computed at most once due to memoization

Space Complexity: O(N * M)

• We're using a 2D array (dp) of size N * M to store the intermediate results
• The recursion stack in the worst case could go up to O(N + M), but this is dominated by the O(N * M) space used by the dp array

after submitting to leetcode: