Longest Common Subsequence in DSA Python - 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

↓

Backtrack from dp[m

↓

Output LCS length and sequence

We build a table to store lengths of common subsequences for all prefixes, then backtrack to find the longest sequence.

Execution Sample

DSA Python

s1 = "ABCBDAB"
s2 = "BDCABA"
# Build dp table
# dp[i][j] = length of LCS of s1[:i] and s2[:j]

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

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Table Update	DP Table State (partial)
1	Initialize DP table	-	-	dp filled with zeros	[[0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [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	dp[1][1]=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	dp[1][2]=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	dp[1][3]=0
5	Compare s1[1]='A' and s2[4]='A'	(1,4)	A vs A	Match, dp[1][4] = dp[0][3] + 1 = 1	dp[1][4]=1
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	dp[1][5]=1
7	Compare s1[1]='A' and s2[6]='A'	(1,6)	A vs A	Match, dp[1][6] = dp[0][5] + 1 = 1	dp[1][6]=1
8	Compare s1[2]='B' and s2[1]='B'	(2,1)	B vs B	Match, dp[2][1] = dp[1][0] + 1 = 1	dp[2][1]=1
9	Compare s1[2]='B' and s2[2]='D'	(2,2)	B vs D	No match, dp[2][2] = max(dp[1][2], dp[2][1]) = 1	dp[2][2]=1
10	Compare s1[2]='B' and s2[3]='C'	(2,3)	B vs C	No match, dp[2][3] = max(dp[1][3], dp[2][2]) = 1	dp[2][3]=1
11	Compare s1[2]='B' and s2[4]='A'	(2,4)	B vs A	No match, dp[2][4] = max(dp[1][4], dp[2][3]) = 1	dp[2][4]=1
12	Compare s1[2]='B' and s2[5]='B'	(2,5)	B vs B	Match, dp[2][5] = dp[1][4] + 1 = 2	dp[2][5]=2
13	Compare s1[2]='B' and s2[6]='A'	(2,6)	B vs A	No match, dp[2][6] = max(dp[1][6], dp[2][5]) = 2	dp[2][6]=2
14	Compare s1[3]='C' and s2[1]='B'	(3,1)	C vs B	No match, dp[3][1] = max(dp[2][1], dp[3][0]) = 1	dp[3][1]=1
15	Compare s1[3]='C' and s2[2]='D'	(3,2)	C vs D	No match, dp[3][2] = max(dp[2][2], dp[3][1]) = 1	dp[3][2]=1
16	Compare s1[3]='C' and s2[3]='C'	(3,3)	C vs C	Match, dp[3][3] = dp[2][2] + 1 = 2	dp[3][3]=2
17	Compare s1[3]='C' and s2[4]='A'	(3,4)	C vs A	No match, dp[3][4] = max(dp[2][4], dp[3][3]) = 2	dp[3][4]=2
18	Compare s1[3]='C' and s2[5]='B'	(3,5)	C vs B	No match, dp[3][5] = max(dp[2][5], dp[3][4]) = 2	dp[3][5]=2
19	Compare s1[3]='C' and s2[6]='A'	(3,6)	C vs A	No match, dp[3][6] = max(dp[2][6], dp[3][5]) = 2	dp[3][6]=2
20	Compare s1[4]='B' and s2[1]='B'	(4,1)	B vs B	Match, dp[4][1] = dp[3][0] + 1 = 1	dp[4][1]=1
21	Compare s1[4]='B' and s2[2]='D'	(4,2)	B vs D	No match, dp[4][2] = max(dp[3][2], dp[4][1]) = 1	dp[4][2]=1
22	Compare s1[4]='B' and s2[3]='C'	(4,3)	B vs C	No match, dp[4][3] = max(dp[3][3], dp[4][2]) = 2	dp[4][3]=2
23	Compare s1[4]='B' and s2[4]='A'	(4,4)	B vs A	No match, dp[4][4] = max(dp[3][4], dp[4][3]) = 2	dp[4][4]=2
24	Compare s1[4]='B' and s2[5]='B'	(4,5)	B vs B	Match, dp[4][5] = dp[3][4] + 1 = 3	dp[4][5]=3
25	Compare s1[4]='B' and s2[6]='A'	(4,6)	B vs A	No match, dp[4][6] = max(dp[3][6], dp[4][5]) = 3	dp[4][6]=3
26	Compare s1[5]='D' and s2[1]='B'	(5,1)	D vs B	No match, dp[5][1] = max(dp[4][1], dp[5][0]) = 1	dp[5][1]=1
27	Compare s1[5]='D' and s2[2]='D'	(5,2)	D vs D	Match, dp[5][2] = dp[4][1] + 1 = 2	dp[5][2]=2
28	Compare s1[5]='D' and s2[3]='C'	(5,3)	D vs C	No match, dp[5][3] = max(dp[4][3], dp[5][2]) = 2	dp[5][3]=2
29	Compare s1[5]='D' and s2[4]='A'	(5,4)	D vs A	No match, dp[5][4] = max(dp[4][4], dp[5][3]) = 2	dp[5][4]=2
30	Compare s1[5]='D' and s2[5]='B'	(5,5)	D vs B	No match, dp[5][5] = max(dp[4][5], dp[5][4]) = 3	dp[5][5]=3
31	Compare s1[5]='D' and s2[6]='A'	(5,6)	D vs A	No match, dp[5][6] = max(dp[4][6], dp[5][5]) = 3	dp[5][6]=3
32	Compare s1[6]='A' and s2[1]='B'	(6,1)	A vs B	No match, dp[6][1] = max(dp[5][1], dp[6][0]) = 1	dp[6][1]=1
33	Compare s1[6]='A' and s2[2]='D'	(6,2)	A vs D	No match, dp[6][2] = max(dp[5][2], dp[6][1]) = 2	dp[6][2]=2
34	Compare s1[6]='A' and s2[3]='C'	(6,3)	A vs C	No match, dp[6][3] = max(dp[5][3], dp[6][2]) = 2	dp[6][3]=2
35	Compare s1[6]='A' and s2[4]='A'	(6,4)	A vs A	Match, dp[6][4] = dp[5][3] + 1 = 3	dp[6][4]=3
36	Compare s1[6]='A' and s2[5]='B'	(6,5)	A vs B	No match, dp[6][5] = max(dp[5][5], dp[6][4]) = 3	dp[6][5]=3
37	Compare s1[6]='A' and s2[6]='A'	(6,6)	A vs A	Match, dp[6][6] = dp[5][5] + 1 = 4	dp[6][6]=4
38	Compare s1[7]='B' and s2[1]='B'	(7,1)	B vs B	Match, dp[7][1] = dp[6][0] + 1 = 1	dp[7][1]=1
39	Compare s1[7]='B' and s2[2]='D'	(7,2)	B vs D	No match, dp[7][2] = max(dp[6][2], dp[7][1]) = 2	dp[7][2]=2
40	Compare s1[7]='B' and s2[3]='C'	(7,3)	B vs C	No match, dp[7][3] = max(dp[6][3], dp[7][2]) = 2	dp[7][3]=2
41	Compare s1[7]='B' and s2[4]='A'	(7,4)	B vs A	No match, dp[7][4] = max(dp[6][4], dp[7][3]) = 3	dp[7][4]=3
42	Compare s1[7]='B' and s2[5]='B'	(7,5)	B vs B	Match, dp[7][5] = dp[6][4] + 1 = 4	dp[7][5]=4
43	Compare s1[7]='B' and s2[6]='A'	(7,6)	B vs A	No match, dp[7][6] = max(dp[6][6], dp[7][5]) = 4	dp[7][6]=4
44	Backtrack from dp[7][6]	-	-	LCS length = 4	LCS found by backtracking: 'BDAB'

💡 All characters compared, DP table fully filled, backtracking completed to find LCS.

Variable Tracker

Variable	Start	After Step 7	After Step 13	After Step 25	After Step 37	Final
i	0	1	2	4	6	7
j	0	6	6	6	6	6
dp[1][4]	0	1	1	1	1	1
dp[2][5]	0	0	2	2	2	2
dp[4][5]	0	0	0	3	3	3
dp[6][6]	0	0	0	0	4	4
LCS length	0	0	0	0	0	4

Key Moments - 3 Insights

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

Because the first row and column represent empty prefixes of the strings, so the longest common subsequence length is zero there, as shown in step 1 of the execution_table.

Why do we take max(dp[i-1][j], dp[i][j-1]) when characters don't match?

Because the LCS up to that point is the longest subsequence found by either ignoring the current character of the first string or the second string, as seen in steps like 2 and 3 where no match occurs.

How do we find the actual LCS string after filling the DP table?

We backtrack from dp[m][n], moving diagonally when characters match and moving up or left when they don't, as summarized in step 44.

Visual Quiz - 3 Questions

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

A 1

B 2

C 3

D 0

💡 Hint

Refer to the 'DP Table Update' and 'DP Table State' columns at step 12.

At which step does the DP table first record a match for characters 'C' and 'C'?

A Step 11

B Step 20

C Step 16

D Step 5

💡 Hint

Check the 'Characters Compared' column for 'C vs C' and the 'DP Table Update' for a match.

If the first string was empty, what would be the LCS length according to the variable_tracker?

A Length is zero

B Length equals the length of second string

C Length equals the length of first string

D Length is one

💡 Hint

Look at the initialization of dp table in step 1 and the first row/column values.

Concept Snapshot

Longest Common Subsequence (LCS):
- Use a 2D DP table dp[m+1][n+1]
- dp[i][j] = length of LCS of s1[:i] and s2[:j]
- If s1[i-1] == s2[j-1], dp[i][j] = dp[i-1][j-1] + 1
- Else dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- Backtrack from dp[m][n] to get LCS string
- Time: O(m*n), Space: O(m*n)

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 LCS length for prefixes s1[:i] and s2[:j]. We fill the table row by row. If characters match, we add 1 to the diagonal cell. If not, we take the max from left or top. After filling, we backtrack from dp[m][n] to find the actual subsequence. The final dp[m][n] gives the LCS length. This method ensures we consider all prefix combinations efficiently.

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 total number of characters in both strings combined.

D. The shortest sequence of characters that can be formed from both strings.

Solution

1. Step 1: Understand the definition of LCS

   The LCS is a sequence that appears in both strings in the same order but not necessarily consecutively.

2. Step 2: Differentiate from substring

   Unlike substring, LCS does not require characters to be contiguous.

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 = longest ordered sequence [OK]

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

Common Mistakes:

• Confusing LCS with longest common substring
• Thinking LCS characters must be consecutive
• Mixing LCS with total string length

2. Which of the following Python code snippets correctly initializes a 2D list for LCS dynamic programming of size (m+1) x (n+1)?

easy

A. dp = [[0] * (m+1)] * (n+1)

B. dp = [[0] * m for _ in range(n)]

C. dp = [0] * (m+1) * (n+1)

D. dp = [[0] * (n+1) for _ in range(m+1)]

Solution

1. Step 1: Understand 2D list initialization

   We need a list of lists with (m+1) rows and (n+1) columns filled with zeros.

2. Step 2: Check each option

   dp = [[0] * (n+1) for _ in range(m+1)] uses list comprehension correctly to create independent rows. dp = [[0] * (m+1)] * (n+1) uses multiplication which creates references to the same list, causing bugs.

3. Final Answer:

   dp = [[0] * (n+1) for _ in range(m+1)] -> Option D

4. Quick Check:

   Use list comprehension for 2D lists [OK]

Hint: Use list comprehension to avoid shared references [OK]

Common Mistakes:

• Using multiplication for 2D lists causing shared rows
• Mixing up m and n dimensions
• Initializing with 1D list instead of 2D

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

def lcs_length(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(lcs_length('AGGTAB', 'GXTXAYB'))

medium

A. 5

B. 4

C. 6

D. 7

Solution

1. Step 1: Understand the LCS calculation

   The function calculates the length of the longest common subsequence between 'AGGTAB' and 'GXTXAYB'.

2. Step 2: Trace the LCS

   A common LCS is 'GTAB' (G at pos 1 or 2 in X, T at 3, A at 4, B at 5; matching positions in Y: G0, T2, A4, B6), length 4. The standard DP code correctly computes dp[6][7] = 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   LCS length = 4 [OK]

Hint: Trace characters matching in order for LCS length [OK]

Common Mistakes:

• Counting longest common substring instead of subsequence
• Miscounting characters due to off-by-one errors
• Confusing length with actual subsequence

4. The following code attempts to compute the LCS length but has a bug. What is the error?

def lcs_bug(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(lcs_bug('ABC', 'AC'))

medium

A. The dp array dimensions are swapped; should be (m+1) x (n+1).

B. The loops iterate over wrong ranges; should start from 0.

C. The comparison uses wrong indices; should be X[i] and Y[j].

D. The return statement returns dp[0][0] instead of dp[m][n].

Solution

1. Step 1: Check dp array initialization

   The dp array is initialized with dimensions (n+1) x (m+1), which is swapped. It should be (m+1) x (n+1) to match loops.

2. Step 2: Consequences of swapped dimensions

   This causes index errors or incorrect results because dp[i][j] expects i in [0..m], j in [0..n].

3. Final Answer:

   The dp array dimensions are swapped; should be (m+1) x (n+1). -> Option A

4. Quick Check:

   dp size matches string lengths [OK]

Hint: Match dp size with string lengths order [OK]

Common Mistakes:

• Swapping m and n in dp initialization
• Starting loops at 0 instead of 1
• Using wrong indices for string characters

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

hard

A. 'BBCA'

B. 'BCBD'

C. 'BDAB'

D. 'BDA'

Solution

1. Step 1: Identify LCS length and candidates

   The LCS length for these strings is 4. Verify which option of length 4 appears in order in both X='ABCBDAB' and Y='BDCABA'.

2. Step 2: Verify each option

   A: 'BDAB' - In X: B(1), D(4), A(5), B(6); in Y: B(0), D(1), A(3), B(4). Order preserved.
   B: 'BCBD' - Requires B then C(2) then B(4) then D after 4, but no D after pos 4 in Y (only D at 1).
   C: 'BBCA' - Requires two B's before C(2) in Y, but only one B at 0 before C(2).
   D: 'BDA' length 3 < 4.

3. Final Answer:

   'BDAB' -> Option C

4. Quick Check:

   Check subsequence order in both strings [OK]

Hint: Check character order in both strings carefully [OK]

Common Mistakes:

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