Longest Common Subsequence in DSA C# - Execution Trace

Concept Flow - Longest Common Subsequence

Start with two strings

↓

Create 2D 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

↓

Backtrack from dp[m

↓

Output LCS length and sequence

↓

End

Build a 2D table comparing characters of two strings, fill it using matches or max of neighbors, then backtrack to find the longest common subsequence.

Execution Sample

DSA C#

string s1 = "ABCBDAB";
string s2 = "BDCABA";
int[,] dp = new int[s1.Length + 1, s2.Length + 1];
// Fill dp table
// Backtrack to find LCS

This code fills a table to find the longest common subsequence length and then backtracks to find the sequence.

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Table Update	Visual DP Table State
1	Initialize DP table	-	-	All zeros in first row and column	[0 0 0 0 0 0 0] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .]
2	Compare s1[1]='A' and s2[1]='B'	(1,1)	'A' vs 'B'	No match, 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 . . . . . .]
3	Compare s1[1]='A' and s2[2]='D'	(1,2)	'A' vs 'D'	No match, 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 s1[1]='A' and s2[3]='C'	(1,3)	'A' vs 'C'	No match, 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 . . . . . .] [0 . . . . . .]
5	Compare s1[1]='A' and s2[4]='A'	(1,4)	'A' vs 'A'	Match, dp[1,4] = dp[0,3] + 1 = 1	[0 0 0 0 0 0 0] [0 0 0 0 1 . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .]
6	Compare s1[1]='A' and s2[5]='B'	(1,5)	'A' vs 'B'	No match, dp[1,5] = max(dp[0,5], dp[1,4]) = 1	[0 0 0 0 0 0 0] [0 0 0 0 1 1 .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .]
7	Compare s1[1]='A' and s2[6]='A'	(1,6)	'A' vs 'A'	Match, dp[1,6] = dp[0,5] + 1 = 1	[0 0 0 0 0 0 0] [0 0 0 0 1 1 1] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .] [0 . . . . . .]
8	Continue filling dp table for all i=2..7 and j=1..6	(2..7,1..6)	Compare characters and update dp accordingly	Fill dp with max subsequence lengths	Final dp table: [0 0 0 0 0 0 0] [0 0 0 0 1 1 1] [0 1 1 1 1 2 2] [0 1 1 2 2 2 2] [0 1 1 2 2 3 3] [0 1 2 2 2 3 3] [0 1 2 2 3 3 4] [0 1 2 2 3 4 4]
9	Backtrack from dp[7,6]	(7,6)	Trace back to find LCS characters	LCS length = 4, sequence = 'BDAB'	Backtracking path: (7,5) 'B' match (6,4) 'A' match (5,2) 'D' match (4,1) 'B' match
10	End	-	-	-	LCS length: 4 LCS sequence: BDAB

💡 All dp table cells filled; backtracking completed to find LCS

Variable Tracker

Variable	Start	After Step 1	After Step 8	After Step 9	Final
dp	Empty 8x7 array	First row and column zeros	Fully filled with LCS lengths	Used for backtracking LCS	Final dp table with LCS lengths
i	Undefined	1	7	7	7
j	Undefined	1	6	6	6
LCS sequence	Empty	Empty	Empty	'BDAB'	'BDAB'
LCS length	0	0	4	4	4

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, so the longest common subsequence length is zero at those points (see execution_table step 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 found by either skipping a character from one string or the other (see execution_table steps 2-7).

How does backtracking from dp[m][n] find the actual LCS sequence?

By moving diagonally when characters match (adding that character), or moving up or left depending on which dp value is larger, reconstructing the sequence backwards (see execution_table step 9).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the dp[1,4] value after comparing 'A' and 'A'?

A 0

B 1

C 2

D Undefined

💡 Hint

Check the 'DP Table Update' column at step 5 in execution_table.

At which step does the dp table become fully filled with LCS lengths?

A Step 1

B Step 7

C Step 8

D Step 9

💡 Hint

Look for the step describing the full dp table completion in execution_table.

According to variable_tracker, what is the LCS length after step 8?

A 4

B 1

C 0

D 3

💡 Hint

Check the 'LCS length' row under 'After Step 8' in variable_tracker.

Concept Snapshot

Longest Common Subsequence (LCS):
- Use 2D dp table of size (m+1)x(n+1)
- dp[i][j] = if chars match: dp[i-1][j-1]+1 else max(dp[i-1][j], dp[i][j-1])
- Initialize first row and column with 0
- Fill table row-wise comparing characters
- Backtrack from dp[m][n] to get LCS sequence
- Result: length and sequence of longest common subsequence

Full Transcript

Longest Common Subsequence finds the longest sequence common to two strings. We create a 2D table where each cell dp[i][j] stores the length of LCS for substrings s1[0..i-1] and s2[0..j-1]. We initialize the first row and column with zeros because an empty string has zero common subsequence. For each pair of characters, 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, we backtrack from dp[m][n] to find the actual LCS sequence by moving diagonally when characters match or moving up/left otherwise. This process gives us both the length and the sequence of the longest common subsequence.

Practice

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

easy

A. The longest sequence of characters appearing in both strings in the same order, not necessarily contiguous

B. The longest sequence of consecutive characters shared by both strings

C. The string formed by concatenating both inputs

D. The shortest string that contains both inputs as subsequences

Solution

1. Step 1: Define subsequence

   A subsequence maintains relative order of characters but does not require them to be contiguous. 'ace' is a subsequence of 'abcde'.

2. Step 2: LCS definition

   LCS is the longest such subsequence common to both strings. For 'ABCBDAB' and 'BDCAB', LCS is 'BCAB' or 'BDAB', length 4.

3. Final Answer:

   Longest common subsequence - same order, not necessarily contiguous. -> Option A

4. Quick Check:

   Subsequence = order preserved, not contiguous. LCS = longest shared one. [OK]

Hint: Subsequence = order preserved, gaps allowed. LCS = longest one common to both strings. [OK]

Common Mistakes:

• Confusing subsequence with substring (substring must be contiguous)
• Thinking LCS is the shortest common supersequence
• Assuming characters must be adjacent

2. For strings X = "ABCD" and Y = "ACDF", what is the length of the LCS?

medium

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Find common subsequences

   Characters in both: A, C, D. Check order: A appears before C in both. C appears before D in both. So 'ACD' is a common subsequence of length 3.

2. Step 2: Can we do better?

   'ABCD' and 'ACDF' share A, C, D in order. B is not in Y. F is not in X. No common subsequence of length 4 exists.

3. Final Answer:

   LCS = "ACD", length 3. -> Option B

4. Quick Check:

   A→C→D in both strings: length 3. [OK]

Hint: Trace common characters in order: A(pos 0,0)→C(pos 2,1)→D(pos 3,2) = 3. [OK]

Common Mistakes:

• Counting all common characters without checking order
• Including B which is not in Y
• Stopping at 2 by missing D

3. In the LCS DP recurrence, when X[i] == Y[j], what is dp[i][j]?

medium

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

B. dp[i-1][j-1] + 1

C. max(dp[i-1][j], dp[i][j-1])

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

Solution

1. Step 1: When characters match

   If X[i] == Y[j], the current characters extend the LCS found without them. We add 1 to the LCS of X[0..i-1] and Y[0..j-1].

2. Step 2: Recurrence

   dp[i][j] = dp[i-1][j-1] + 1. We extend the diagonal neighbor by 1.

3. Step 3: When they don't match

   dp[i][j] = max(dp[i-1][j], dp[i][j-1]) - take the best from skipping either character.

4. Final Answer:

   dp[i-1][j-1] + 1 -> Option B

5. Quick Check:

   Match → diagonal + 1. No match → max of left and above. [OK]

Hint: Match: diagonal + 1. No match: max(left, above). [OK]

Common Mistakes:

• Using dp[i-1][j-1] without adding 1
• Using max formula when characters match
• Adding 1 to dp[i][j-1] instead of diagonal

4. What is the time and space complexity of the standard 2D DP LCS solution for strings of length m and n?

medium

A. Time O(m+n), Space O(m+n)

B. Time O(m×n), Space O(m×n)

C. Time O(m×n), Space O(min(m,n))

D. Time O(2^n), Space O(n)

Solution

1. Step 1: Time complexity

   We fill a 2D table of size (m+1)×(n+1), computing each cell in O(1). Total: O(m×n).

2. Step 2: Space complexity

   The full 2D DP table requires O(m×n) space. Space can be optimized to O(min(m,n)) using two rows, but standard solution uses O(m×n).

3. Final Answer:

   Time O(m×n), Space O(m×n) -> Option B

4. Quick Check:

   Standard 2D table = O(m×n) both time and space. [OK]

Hint: Standard LCS: O(m×n) time and space (2D table). [OK]

Common Mistakes:

• Saying O(m+n) which is linear - LCS needs quadratic
• Reporting space-optimized O(min(m,n)) for the standard solution
• Confusing with exponential recursion without memoization

5. In C#, after filling the LCS DP table for X="AGGTAB" and Y="GXTXAYB", what value does dp[6][7] hold?

hard

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Identify LCS

   X = 'AGGTAB', Y = 'GXTXAYB'. Common subsequences include 'GTAB' (length 4): G(1,0)→T(2,3)→A(4,4)→B(5,6).

2. Step 2: Verify length 4

   G: appears in both at valid positions. T: X[2]='G',X[2]='G'... Let's check: X='A,G,G,T,A,B'. Y='G,X,T,X,A,Y,B'. Common: G(X[1],Y[0]), T(X[3],Y[2]), A(X[4],Y[4]), B(X[5],Y[6]) → GTAB length 4.

3. Final Answer:

   dp[6][7] = 4 -> Option B

4. Quick Check:

   LCS of 'AGGTAB' and 'GXTXAYB' is 'GTAB' = length 4. [OK]

Hint: LCS('AGGTAB','GXTXAYB') = 'GTAB' = 4. This is a classic example - memorize it. [OK]

Common Mistakes:

• Confusing LCS length with string length
• Incorrectly tracing the DP table
• Getting 3 by missing one character in the subsequence