Longest Common Subsequence in DSA Javascript

Mental Model

Find the longest sequence of characters that appear in the same order in both strings, but not necessarily consecutively.

Analogy: Imagine two friends telling stories with some common events. The longest common subsequence is like the longest list of shared events they both mention in the same order, even if they skip some details.

String1: A B C D G H
String2: A E D F H R

LCS path:
A ->   -> D ->   -> H

Where arrows show matching characters in order but not necessarily side by side.

Dry Run Walkthrough

Input: string1: "ABCDGH", string2: "AEDFHR"

Goal: Find the longest common subsequence between the two strings

Step 1: Initialize a 2D array dp with size (7 x 7) filled with 0 (lengths for empty prefixes)

dp matrix with all zeros:
[0,0,0,0,0,0,0]
[0,0,0,0,0,0,0]
[0,0,0,0,0,0,0]
[0,0,0,0,0,0,0]
[0,0,0,0,0,0,0]
[0,0,0,0,0,0,0]
[0,0,0,0,0,0,0]

Why: We need a base to build subsequence lengths for all prefixes of both strings

Step 2: Compare characters at positions (1,1): 'A' and 'A' match, set dp[1][1] = dp[0][0] + 1 = 1

dp[1][1] = 1, rest zeros

Why: Matching characters increase subsequence length by 1

Step 3: Compare (2,2): 'B' and 'E' do not match, set dp[2][2] = max(dp[1][2], dp[2][1]) = max(0,1) = 1

dp[2][2] = 1

Why: No match, so take the best subsequence length from previous prefixes

Step 4: Compare (4,3): 'D' and 'D' match, set dp[4][3] = dp[3][2] + 1 = 2

dp[4][3] = 2

Why: Matching characters extend the subsequence length

Step 5: Compare (6,5): 'H' and 'H' match, set dp[6][5] = dp[5][4] + 1 = 3

dp[6][5] = 3

Why: Another match extends the subsequence length

Step 6: Final dp matrix bottom-right value dp[6][6] = 3, which is the length of LCS

dp[6][6] = 3

Why: The bottom-right cell holds the length of the longest common subsequence

Step 7: Trace back from dp[6][6] to find the LCS string: 'A', 'D', 'H'

LCS = "ADH"

Why: Backtracking recovers the actual subsequence from dp table

Result:

LCS length = 3
LCS string = "ADH"

Annotated Code

DSA Javascript

class LCS {
  static longestCommonSubsequence(str1, str2) {
    const m = str1.length, n = str2.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        if (str1[i - 1] === str2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1] + 1; // extend subsequence length
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // best previous length
        }
      }
    }

    // Backtrack to find the subsequence string
    let i = m, j = n;
    let lcsStr = '';
    while (i > 0 && j > 0) {
      if (str1[i - 1] === str2[j - 1]) {
        lcsStr = str1[i - 1] + lcsStr; // add matching char
        i--;
        j--;
      } else if (dp[i - 1][j] > dp[i][j - 1]) {
        i--; // move up
      } else {
        j--; // move left
      }
    }

    return { length: dp[m][n], sequence: lcsStr };
  }
}

// Driver code
const str1 = "ABCDGH";
const str2 = "AEDFHR";
const result = LCS.longestCommonSubsequence(str1, str2);
console.log(`LCS length = ${result.length}`);
console.log(`LCS string = "${result.sequence}"`);

if (str1[i - 1] === str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1;

extend subsequence length when characters match

else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

choose best subsequence length from previous prefixes when no match

while (i > 0 && j > 0) { if (str1[i - 1] === str2[j - 1]) { lcsStr = str1[i - 1] + lcsStr; i--; j--;

backtrack to build LCS string by adding matching characters

else if (dp[i - 1][j] > dp[i][j - 1]) { i--;

move up in dp table if upper cell has longer subsequence

else { j--;

move left in dp table if left cell has longer or equal subsequence

Output

LCS length = 3

LCS string = "ADH"

Complexity Analysis

Time: O(m*n) because we fill a 2D table of size m by n once

Space: O(m*n) because we store subsequence lengths for all prefix pairs

vs Alternative: Naive recursive approach is exponential O(2^(m+n)) due to repeated subproblems; DP reduces it to polynomial time

Edge Cases

One or both strings empty

LCS length is 0 and subsequence is empty string

DSA Javascript

const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));

Strings with no common characters

LCS length is 0 and subsequence is empty string

DSA Javascript

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

Strings are identical

LCS length equals string length and subsequence is the string itself

DSA Javascript

if (str1[i - 1] === str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; }

When to Use This Pattern

When you need to find the longest sequence common to two sequences in order but not necessarily contiguous, use the Longest Common Subsequence pattern with dynamic programming.

Common Mistakes

Mistake: Confusing subsequence with substring and expecting characters to be consecutive
Fix: Remember subsequence allows skipping characters, so check characters in order but not necessarily adjacent

Mistake: Not initializing dp array with extra row and column for empty prefixes
Fix: Initialize dp with size (m+1) x (n+1) to handle empty string cases properly

Mistake: Incorrect backtracking direction causing wrong subsequence reconstruction
Fix: Backtrack by moving diagonally on match, else move towards the cell with larger dp value

Summary

Finds the longest sequence of characters common to two strings in order but not necessarily contiguous.

Use when comparing two sequences to find their shared ordered pattern, such as in diff tools or DNA sequence analysis.

The key insight is building a table of subsequence lengths for all prefixes and backtracking to recover the sequence.

Practice

1. What does the Longest Common Subsequence (LCS) between two strings represent?

easy

A. The longest sequence of characters that appear in both strings in the same order, but not necessarily consecutively

B. The longest substring that appears exactly the same in both strings

C. The shortest sequence that can be formed from both strings

D. The total number of characters in both strings combined

Solution

1. Step 1: Understand the definition of LCS

   The LCS is about finding a sequence that appears in both strings in the same order, but characters do not need to be next to each other.

2. Step 2: Differentiate LCS from substring

   A substring requires characters to be consecutive, but LCS allows gaps, so it is not necessarily a substring.

3. Final Answer:

   The longest sequence of characters that appear in both strings in the same order, but not necessarily consecutively -> Option A

4. Quick Check:

   LCS means longest common sequence, not substring [OK]

Hint: LCS allows gaps; substring does not [OK]

Common Mistakes:

• Confusing LCS with longest common substring
• Thinking characters must be consecutive
• Assuming LCS is the combined length

2. Which of the following is the correct way to initialize a 2D array dp of size (m+1) x (n+1) with zeros in JavaScript for LCS dynamic programming?

easy

A. const dp = Array(m+1).fill(Array(n+1).fill(0));

B. const dp = Array.from({length: m+1}, () => Array(n+1).fill(0));

C. const dp = new Array(m+1).map(new Array(n+1).fill(0));

D. const dp = Array(m+1).map(Array(n+1).fill(0));

Solution

1. Step 1: Understand how to create independent inner arrays

   Using Array.from with a function creates new inner arrays for each row, avoiding shared references.

2. Step 2: Analyze each option

   Array(m+1).fill(Array(n+1).fill(0)) shares the same inner array for all rows, causing bugs. Options C and D pass an array to map() instead of a function, causing a TypeError. Array.from({length: m+1}, () => Array(n+1).fill(0)) correctly creates independent arrays.

3. Final Answer:

   const dp = Array.from({length: m+1}, () => Array(n+1).fill(0)); -> Option B

4. Quick Check:

   Use Array.from with function for 2D arrays [OK]

Hint: Use Array.from with function to avoid shared inner arrays [OK]

Common Mistakes:

• Using fill with array directly causing shared references
• Passing an array to map() instead of a function
• Not initializing inner arrays properly

3. What is the output of the following JavaScript code that calculates the length of the LCS for strings s1 = 'abcde' and s2 = 'ace'?

function lcsLength(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i-1] === s2[j-1]) {
        dp[i][j] = dp[i-1][j-1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }
  return dp[m][n];
}
console.log(lcsLength('abcde', 'ace'));

medium

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Trace matching characters between 'abcde' and 'ace'

   The common subsequence is 'ace' with length 3.

2. Step 2: Confirm DP calculation

   The code correctly fills dp table and returns dp[5][3] = 3 as the LCS length.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   LCS('abcde','ace') = 'ace' length 3 [OK]

Hint: Count matching chars in order, skipping mismatches [OK]

Common Mistakes:

• Counting only consecutive matches (substring)
• Confusing length with total characters
• Off-by-one errors in indexing

4. The following code attempts to compute the LCS length but has a bug. What is the error?

function lcsLength(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array(m+1).fill(Array(n+1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i-1] === s2[j-1]) {
        dp[i][j] = dp[i-1][j-1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }
  return dp[m][n];
}

medium

A. The inner arrays in dp share the same reference causing incorrect updates

B. The loops start from 0 instead of 1

C. The dp array is not initialized with zeros

D. The comparison s1[i-1] === s2[j-1] is incorrect

Solution

1. Step 1: Analyze dp initialization

   Using fill with an array fills dp with references to the same inner array, so all rows share one array.

2. Step 2: Understand impact on updates

   Updating dp[i][j] changes all rows at column j, corrupting the DP table and causing wrong results.

3. Final Answer:

   The inner arrays in dp share the same reference causing incorrect updates -> Option A

4. Quick Check:

   Array fill shares references, use Array.from instead [OK]

Hint: Avoid fill with arrays; use Array.from for 2D arrays [OK]

Common Mistakes:

• Using fill with arrays causing shared references
• Starting loops at 0 causing index errors
• Incorrect character comparison

5. Given two strings s1 = 'AGGTAB' and s2 = 'GXTXAYB', which of the following is a valid Longest Common Subsequence (LCS)?

hard

A. "GXAYB"

B. "GXTAB"

C. "AGTXB"

D. "GTAB"

Solution

1. Step 1: Identify common subsequences in order

   Check which sequences appear in both strings in order without rearranging characters.

2. Step 2: Validate each option

   "GTAB" appears in both strings in order. Options A, B, and C contain characters out of order or extra characters not matching subsequence rules.

3. Final Answer:

   "GTAB" -> Option D

4. Quick Check:

   Valid LCS must appear in both strings in order [OK]

Hint: Check order and presence of characters in both strings [OK]

Common Mistakes:

• Choosing sequences with characters out of order
• Including characters not in both strings
• Confusing subsequence with substring