Longest Common Subsequence in DSA C - 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):

↓

i

↓

i

↓

DP table filled

↓

Trace back from dp[m

↓

Output LCS length and sequence

↓

End

Build a table to store lengths of common subsequences for prefixes, then trace back to find the longest sequence.

Execution Sample

DSA C

int lcs(char *X, char *Y) {
  int m = strlen(X), n = strlen(Y);
  int dp[m+1][n+1];
  for (int i=0; i<=m; i++) dp[i][0] = 0;
  for (int j=0; j<=n; j++) dp[0][j] = 0;
  for (int i=1; i<=m; i++) {
    for (int 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] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1];
    }
  }
  return dp[m][n];
}

This code calculates the length of the longest common subsequence between two strings X and Y using dynamic programming.

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Table Update	DP Table State (partial)
1	Initialize dp[0][*] and dp[*][0]	-	-	dp[i][0]=0 and dp[0][j]=0	[Row0 and Col0 all zeros]
2	Compare X[0] and Y[0]	(1,1)	X='A', Y='B'	No match, dp[1][1] = max(dp[0][1], dp[1][0]) = 0	[[0,0,0],[0,0,...],...]
3	Compare X[0] and Y[1]	(1,2)	X='A', Y='D'	No match, dp[1][2] = max(dp[0][2], dp[1][1]) = 0	[[0,0,0],[0,0,0],...]
4	Compare X[0] and Y[2]	(1,3)	X='A', Y='C'	No match, dp[1][3] = max(dp[0][3], dp[1][2]) = 0	[[0,0,0,0],[0,0,0,0],...]
5	Compare X[0] and Y[3]	(1,4)	X='A', Y='A'	Match, dp[1][4] = dp[0][3] + 1 = 1	[[0,0,0,0,0],[0,0,0,0,1],...]
6	Compare X[1] and Y[0]	(2,1)	X='B', Y='B'	Match, dp[2][1] = dp[1][0] + 1 = 1	[[0,0,0,0,0],[0,0,0,0,1],[0,1,...],...]
7	Compare X[1] and Y[1]	(2,2)	X='B', Y='D'	No match, dp[2][2] = max(dp[1][2], dp[2][1]) = 1	[... dp[2][2]=1 ...]
8	Compare X[1] and Y[2]	(2,3)	X='B', Y='C'	No match, dp[2][3] = max(dp[1][3], dp[2][2]) = 1	[... dp[2][3]=1 ...]
9	Compare X[1] and Y[3]	(2,4)	X='B', Y='A'	No match, dp[2][4] = max(dp[1][4], dp[2][3]) = 1	[... dp[2][4]=1 ...]
10	Compare X[2] and Y[0]	(3,1)	X='C', Y='B'	No match, dp[3][1] = max(dp[2][1], dp[3][0]) = 1	[... dp[3][1]=1 ...]
11	Compare X[2] and Y[1]	(3,2)	X='C', Y='D'	No match, dp[3][2] = max(dp[2][2], dp[3][1]) = 1	[... dp[3][2]=1 ...]
12	Compare X[2] and Y[2]	(3,3)	X='C', Y='C'	Match, dp[3][3] = dp[2][2] + 1 = 2	[... dp[3][3]=2 ...]
13	Compare X[2] and Y[3]	(3,4)	X='C', Y='A'	No match, dp[3][4] = max(dp[2][4], dp[3][3]) = 2	[... dp[3][4]=2 ...]
14	Compare X[3] and Y[0]	(4,1)	X='D', Y='B'	No match, dp[4][1] = max(dp[3][1], dp[4][0]) = 1	[... dp[4][1]=1 ...]
15	Compare X[3] and Y[1]	(4,2)	X='D', Y='D'	Match, dp[4][2] = dp[3][1] + 1 = 2	[... dp[4][2]=2 ...]
16	Compare X[3] and Y[2]	(4,3)	X='D', Y='C'	No match, dp[4][3] = max(dp[3][3], dp[4][2]) = 2	[... dp[4][3]=2 ...]
17	Compare X[3] and Y[3]	(4,4)	X='D', Y='A'	No match, dp[4][4] = max(dp[3][4], dp[4][3]) = 2	[... dp[4][4]=2 ...]
18	DP table complete	-	-	LCS length = dp[4][4] = 2	[Full dp table filled]
19	Trace back to find LCS	-	-	LCS sequence found: 'BA' or 'CA' depending on path	-
20	End	-	-	Return LCS length 2	-

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

Variable Tracker

Variable	Start	After Step 5	After Step 12	After Step 15	Final
i	0	1	3	4	4
j	0	4	3	2	4
dp[1][4]	uninitialized	1	1	1	1
dp[3][3]	uninitialized	0	2	2	2
dp[4][2]	uninitialized	0	0	2	2
LCS length	0	0	0	0	2

Key Moments - 3 Insights

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

Because they represent comparisons with an empty string prefix, so the longest common subsequence length is zero at those points (see Step 1 in execution_table).

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

Because a matching character extends the previous longest subsequence by one (see Steps 5, 6, 12, 15 where dp[i][j] = dp[i-1][j-1] + 1).

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

Because the LCS up to that point is the longest subsequence found by either skipping a character from one string or the other (see Steps 2, 3, 4, 7, 8, 9).

Visual Quiz - 3 Questions

Look at the execution_table at Step 12. What is the value of dp[3][3] after comparing X[2] and Y[2]?

A 2

B 3

C 1

D 0

💡 Hint

Check the DP Table Update column at Step 12 in execution_table.

At which step does the DP table first record a match and increase the subsequence length?

A Step 2

B Step 7

C Step 5

D Step 10

💡 Hint

Look for the first step where 'Match' appears in the Operation column in execution_table.

According to variable_tracker, what is the final LCS length after all steps?

A 3

B 2

C 1

D 4

💡 Hint

Check the 'LCS length' row in variable_tracker under the 'Final' column.

Concept Snapshot

Longest Common Subsequence (LCS):
- Use a 2D dp table of size (m+1)x(n+1) for strings of length m and n.
- Initialize first row and column to 0.
- If characters match: dp[i][j] = dp[i-1][j-1] + 1.
- Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
- Result is dp[m][n], trace back to find the sequence.

Full Transcript

Longest Common Subsequence finds the longest sequence common to two strings. We create a table dp where dp[i][j] stores the length of LCS of prefixes X[0..i-1] and Y[0..j-1]. We fill the first row and column with zeros because an empty string has no common subsequence. For each character pair, if they match, we add 1 to dp[i-1][j-1]. If not, we take the maximum of dp[i-1][j] and dp[i][j-1]. After filling the table, dp[m][n] gives the length of the LCS. We can trace back from dp[m][n] to find the actual subsequence. This method uses dynamic programming to avoid repeated work and efficiently find the LCS length and sequence.