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.

Practice

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

easy

A. The total number of characters in both strings combined

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

C. The shortest sequence of characters to convert one string into another

D. The longest substring that appears in both strings consecutively

Solution

1. Step 1: Understand the definition of LCS

   The LCS is the longest sequence that appears in both strings in the same order but not necessarily next to each other.

2. Step 2: Differentiate from substring and edit distance

   Unlike substring, LCS does not require characters to be consecutive. It is not about shortest edits either.

3. Final Answer:

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

4. Quick Check:

   LCS means longest common sequence, not substring or edits [OK]

Hint: LCS is about order, not consecutive characters [OK]

Common Mistakes:

• Confusing LCS with longest common substring
• Thinking LCS requires consecutive characters
• Mixing LCS with edit distance or shortest transformation

2. Which of the following TypeScript function signatures correctly represents a function to compute LCS length between two strings s1 and s2?

easy

A. function lcsLength(s1: string, s2: string): string[]

B. function lcsLength(s1: number[], s2: number[]): string

C. function lcsLength(s1: string, s2: string): void

D. function lcsLength(s1: string, s2: string): number

Solution

1. Step 1: Identify input and output types for LCS length

   The function takes two strings and returns a number representing the length of their LCS.

2. Step 2: Check each option's signature

   function lcsLength(s1: string, s2: string): number matches input strings and returns a number. Others either use wrong input types or return wrong types.

3. Final Answer:

   function lcsLength(s1: string, s2: string): number -> Option D

4. Quick Check:

   Input strings, output number for LCS length [OK]

Hint: LCS length function returns a number, inputs are strings [OK]

Common Mistakes:

• Using arrays instead of strings as input
• Returning string or void instead of number
• Confusing LCS length with LCS sequence output

3. What is the output of the following TypeScript code snippet?

function lcsLength(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp: number[][] = 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 (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('AGGTAB', 'GXTXAYB'))

medium

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Understand the LCS dynamic programming table

   The code builds a 2D table dp where dp[i][j] stores LCS length of s1[0..i-1] and s2[0..j-1].

2. Step 2: Trace LCS for 'AGGTAB' and 'GXTXAYB'

   The LCS is 'GTAB' with length 4, but careful tracing shows length 4 is correct. However, the known LCS length for these strings is 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   LCS('AGGTAB','GXTXAYB') = 4 [OK]

Hint: Trace dp table or recall classic example LCS length 4 [OK]

Common Mistakes:

• Confusing LCS length with substring length
• Miscounting matching characters
• Off-by-one errors in indexing

4. Identify the bug in the following TypeScript code that attempts to compute the LCS length:

function lcsLength(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp: number[][] = Array(m).fill(Array(n).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 - 1][n - 1];
}

medium

A. dp array initialization shares inner arrays causing incorrect updates

B. Loop indices should start from 0 instead of 1

C. Return statement should be dp[m][n] instead of dp[m - 1][n - 1]

D. Comparison should be s1[i] === s2[j] instead of s1[i - 1] === s2[j - 1]

Solution

1. Step 1: Analyze dp array initialization

   Using Array(m).fill(Array(n).fill(0)) creates m references to the same inner array, causing shared rows.

2. Step 2: Understand impact on dp updates

   Updating dp[i][j] affects all rows because they point to the same array, corrupting the dp table.

3. Final Answer:

   dp array initialization shares inner arrays causing incorrect updates -> Option A

4. Quick Check:

   Array fill with same inner array causes shared references [OK]

Hint: Use map to create independent inner arrays for dp [OK]

Common Mistakes:

• Using fill with array causes shared references
• Incorrect dp return indices
• Off-by-one errors in loops

5. Given two strings s1 = 'ABCBDAB' and s2 = 'BDCABA', which of the following is a valid Longest Common Subsequence?

hard

A. 'BDCA'

B. 'BCBD'

C. 'BDAB'

D. 'BDA'

Solution

1. Step 1: Determine length of LCS

   The LCS length for these strings is 4.

2. Step 2: Check each option for validity and length

   'BDAB' is length 4 and appears in order in both strings. Others are either shorter or invalid sequences.

3. Final Answer:

   'BDAB' -> Option C

4. Quick Check:

   Valid LCS must be subsequence and max length 4 [OK]

Hint: Check subsequence order and length equals LCS length [OK]

Common Mistakes:

• Choosing subsequences not in order in both strings
• Picking shorter subsequences ignoring max length
• Confusing substring with subsequence