Longest Common Subsequence in DSA Typescript - Execution Trace

Concept Flow - Longest Common Subsequence

Start with two strings

↓

Create DP table with sizes (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

Build a table comparing prefixes of two strings, fill it using matches or max of neighbors, then trace back to find the longest common subsequence.

Execution Sample

DSA Typescript

function lcs(X: string, Y: string): string {
  const m = X.length, n = Y.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 (X[i-1] === Y[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]);
    }
  }
  let res = '';
  let i = m, j = n;
  while (i > 0 && j > 0) {
    if (X[i-1] === Y[j-1]) {
      res = X[i-1] + res;
      i--; j--;
    } else if (dp[i-1][j] > dp[i][j-1]) i--;
    else j--;
  }
  return res;
}

This code builds a table to find the longest common subsequence of two strings and then reconstructs the sequence by tracing back.

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Table Update	DP Table State Snapshot
1	Initialize DP table	-	-	All zeros	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
2	Compare X[0]='A' and Y[0]='B'	(1,1)	A vs B	dp[1][1] = max(dp[0][1], dp[1][0]) = 0	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
3	Compare X[0]='A' and Y[1]='D'	(1,2)	A vs D	dp[1][2] = max(dp[0][2], dp[1][1]) = 0	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
4	Compare X[0]='A' and Y[2]='C'	(1,3)	A vs C	dp[1][3] = max(dp[0][3], dp[1][2]) = 0	[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
5	Compare X[1]='B' and Y[0]='B'	(2,1)	B vs B	dp[2][1] = dp[1][0] + 1 = 1	[[0,0,0,0],[0,0,0,0],[0,1,0,0],[0,0,0,0]]
6	Compare X[1]='B' and Y[1]='D'	(2,2)	B vs D	dp[2][2] = max(dp[1][2], dp[2][1]) = 1	[[0,0,0,0],[0,0,0,0],[0,1,1,0],[0,0,0,0]]
7	Compare X[1]='B' and Y[2]='C'	(2,3)	B vs C	dp[2][3] = max(dp[1][3], dp[2][2]) = 1	[[0,0,0,0],[0,0,0,0],[0,1,1,1],[0,0,0,0]]
8	Compare X[2]='C' and Y[0]='B'	(3,1)	C vs B	dp[3][1] = max(dp[2][1], dp[3][0]) = 1	[[0,0,0,0],[0,0,0,0],[0,1,1,1],[0,1,0,0]]
9	Compare X[2]='C' and Y[1]='D'	(3,2)	C vs D	dp[3][2] = max(dp[2][2], dp[3][1]) = 1	[[0,0,0,0],[0,0,0,0],[0,1,1,1],[0,1,1,0]]
10	Compare X[2]='C' and Y[2]='C'	(3,3)	C vs C	dp[3][3] = dp[2][2] + 1 = 2	[[0,0,0,0],[0,0,0,0],[0,1,1,1],[0,1,1,2]]
11	Traceback start	(3,3)	-	Start at dp[3][3]=2	-
12	X[2]=C equals Y[2]=C	(3,3)	C vs C	Add 'C' to result, move i=2, j=2	-
13	X[1]=B vs Y[1]=D	(2,2)	B vs D	dp[1][2]=0 < dp[2][1]=1, move i=2, j=1	-
14	X[1]=B equals Y[0]=B	(2,1)	B vs B	Add 'B' to result, move i=1, j=0	-
15	Traceback ends	(1,0)	-	j=0 reached, stop	-

💡 Traceback ends when either i or j reaches 0, meaning no more characters to compare.

Variable Tracker

Variable	Start	After Step 5	After Step 10	After Step 15
i	3	3	3	1
j	3	1	3	0
dp[3][3]	0	0	2	2
LCS Result	""	""	""	"BC"

Key Moments - 3 Insights

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

Because matching characters extend the previous longest subsequence by one, as shown in step 10 where dp[3][3] = dp[2][2] + 1.

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

Because the longest subsequence up to (i,j) is the best between ignoring one character from either string, as seen in steps 2-4 and 6-9.

How does the traceback find the actual subsequence?

By moving diagonally when characters match (adding to result) or moving up/left based on dp values when they don't, as shown in steps 12-14.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the value of dp[3][3]?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'DP Table Update' and 'DP Table State Snapshot' columns at step 10.

At which step does the traceback add the character 'B' to the result?

A Step 12

B Step 13

C Step 14

D Step 15

💡 Hint

Look at the 'Operation' and 'DP Table Update' columns during traceback steps.

If the characters at X[i-1] and Y[j-1] never match, how would the DP table values change?

A They would all be zero except first row and column

B They would increase by 1 each step

C They would be the sum of indices i and j

D They would be random values

💡 Hint

Refer to the logic in steps 2-4 where no matches cause dp values to remain zero.

Concept Snapshot

Longest Common Subsequence (LCS):
- Use a 2D DP table dp[m+1][n+1] for strings X and Y
- dp[i][j] = dp[i-1][j-1] + 1 if X[i-1] == Y[j-1]
- Else dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- Fill table row-wise, then traceback from dp[m][n]
- Traceback adds matching chars to result, moving diagonally
- Result is the longest subsequence common to both strings

Full Transcript

The Longest Common Subsequence problem finds the longest sequence of characters that appear in the same order in two strings. We start by creating a table with rows and columns one more than the lengths of the two strings. We fill the first row and column with zeros because an empty string has zero common subsequence with any string. Then, for each character pair from the two strings, if they match, we add one to the value from the diagonal cell above-left. If they don't match, we take the maximum value from the cell above or to the left. After filling the table, we trace back from the bottom-right corner to find the actual subsequence by moving diagonally when characters match or moving up or left depending on which neighbor has the larger value. This process gives us the longest common subsequence string. The execution table shows each step of filling the table and the traceback process, while the variable tracker shows how indices and the result string change. Key moments clarify why we add one on matches, why we take max on mismatches, and how traceback works. The visual quiz tests understanding of table values and traceback steps. The concept snapshot summarizes the approach and rules for LCS.