Longest Common Subsequence in DSA Javascript - Execution Trace

Concept Flow - Longest Common Subsequence

Start with two strings

↓

Create DP table with size (m+1)x(n+1)

↓

Fill first row and column with 0

↓

For each character pair (i,j):

↓

If chars match: dp[i

↓

Else: dp[i

↓

DP table filled

↓

Trace back from dp[m

↓

Output LCS length and sequence

↓

End

We build a table comparing characters of two strings, filling it step-by-step to find the longest sequence common to both, then trace back to get the sequence.

Execution Sample

DSA Javascript

const lcs = (a, b) => {
  const dp = Array(a.length+1).fill().map(() => Array(b.length+1).fill(0));
  for(let i=1; i<=a.length; i++) {
    for(let j=1; j<=b.length; j++) {
      if(a[i-1] === b[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[a.length][b.length];
};

This code builds a 2D table to find the length of the longest common subsequence between two strings.

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Table Update	DP Table State (partial)
1	Initialize DP table	-	-	All zeros	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
2	Compare chars	(1,1)	A vs A	dp[1][1] = dp[0][0] + 1 = 1	[[0,0,0,0],[0,1,0,0],[0,0,0,0],[0,0,0,0]]
3	Compare chars	(1,2)	A vs B	dp[1][2] = max(dp[0][2], dp[1][1]) = 1	[[0,0,0,0],[0,1,1,0],[0,0,0,0],[0,0,0,0]]
4	Compare chars	(1,3)	A vs C	dp[1][3] = max(dp[0][3], dp[1][2]) = 1	[[0,0,0,0],[0,1,1,1],[0,0,0,0],[0,0,0,0]]
5	Compare chars	(2,1)	B vs A	dp[2][1] = max(dp[1][1], dp[2][0]) = 1	[[0,0,0,0],[0,1,1,1],[0,1,0,0],[0,0,0,0]]
6	Compare chars	(2,2)	B vs B	dp[2][2] = dp[1][1] + 1 = 2	[[0,0,0,0],[0,1,1,1],[0,1,2,0],[0,0,0,0]]
7	Compare chars	(2,3)	B vs C	dp[2][3] = max(dp[1][3], dp[2][2]) = 2	[[0,0,0,0],[0,1,1,1],[0,1,2,2],[0,0,0,0]]
8	Compare chars	(3,1)	C vs A	dp[3][1] = max(dp[2][1], dp[3][0]) = 1	[[0,0,0,0],[0,1,1,1],[0,1,2,2],[0,1,0,0]]
9	Compare chars	(3,2)	C vs B	dp[3][2] = max(dp[2][2], dp[3][1]) = 2	[[0,0,0,0],[0,1,1,1],[0,1,2,2],[0,1,2,0]]
10	Compare chars	(3,3)	C vs C	dp[3][3] = dp[2][2] + 1 = 3	[[0,0,0,0],[0,1,1,1],[0,1,2,2],[0,1,2,3]]
11	End	-	-	LCS length = dp[3][3] = 3	Final DP table as above

💡 All characters compared, DP table fully filled, LCS length found at dp[m][n]

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 10	Final
dp	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]	[[0,0,0,0],[0,1,0,0],[0,0,0,0],[0,0,0,0]]	[[0,0,0,0],[0,1,1,1],[0,1,2,0],[0,0,0,0]]	[[0,0,0,0],[0,1,1,1],[0,1,2,2],[0,1,2,3]]	[[0,0,0,0],[0,1,1,1],[0,1,2,2],[0,1,2,3]]
i	0	1	2	3	3
j	0	1	2	3	3

Key Moments - 3 Insights

Why do we add 1 to dp[i-1][j-1] when characters match?

Because matching characters extend the common subsequence by one, so we add 1 to the length found without these characters (dp[i-1][j-1]). See execution_table rows 2, 6, and 10.

Why do we take max of dp[i-1][j] and dp[i][j-1] when characters don't match?

Because the longest subsequence so far could be from skipping one character either in string a or b. We pick the longer subsequence found so far. See execution_table rows 3, 4, 5, 7, 8, 9.

Why do we initialize the first row and column with zeros?

Because an empty string compared with any string has zero common subsequence length. This sets the base case for building the DP table. See execution_table row 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of dp[2][2]?

A 1

B 2

C 0

D 3

💡 Hint

Check the DP Table Update column at step 6 in execution_table.

At which step does the DP table first get a value of 3?

A Step 10

B Step 9

C Step 11

D Step 6

💡 Hint

Look at the DP Table Update and DP Table State columns in execution_table.

If characters at (i,j) never match, what will dp[i][j] be based on?

A dp[i-1][j-1] + 1

B max(dp[i-1][j], dp[i][j-1])

C 0

D dp[i][j-1] + 1

💡 Hint

Refer to the 'DP Table Update' column for non-matching characters in execution_table.

Concept Snapshot

Longest Common Subsequence (LCS):
- Use 2D DP table dp[m+1][n+1] for strings of length m and n
- dp[i][j] = length of LCS of a[0..i-1], b[0..j-1]
- If chars match: dp[i][j] = dp[i-1][j-1] + 1
- Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- Result at dp[m][n] is LCS length
- Trace back dp to find actual subsequence

Full Transcript

Longest Common Subsequence finds the longest sequence common to two strings. We create a table where each cell dp[i][j] stores the length of the LCS for the first i characters of string a and first j characters of string b. We fill the table row by row. If characters match, we add 1 to the diagonal cell dp[i-1][j-1]. If not, we take the maximum from the left or top cell. After filling the table, dp[m][n] gives the length of the LCS. We can then trace back from dp[m][n] to find the actual subsequence. This method uses dynamic programming to avoid repeated work and efficiently find the solution.

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