Longest Common Subsequence in DSA Python - Build from Scratch

Longest Common Subsequence

📖 Scenario: You are working on a text comparison tool that helps find the longest common subsequence (LCS) between two strings. This is useful in applications like spell checkers, DNA sequence analysis, and file comparison.

🎯 Goal: Build a program that finds the length of the longest common subsequence between two given strings using dynamic programming.

📋 What You'll Learn

Create two string variables with exact values

Create a 2D list (matrix) to store LCS lengths

Use nested loops to fill the matrix based on LCS rules

Print the final LCS length

💡 Why This Matters

🌍 Real World

Longest common subsequence is used in text comparison tools, DNA sequence analysis, and version control systems to find similarities between sequences.

💼 Career

Understanding LCS and dynamic programming is important for software engineers working on algorithms, bioinformatics, and data comparison tasks.

1

Create the input strings

Create two string variables called string1 and string2 with the exact values "AGGTAB" and "GXTXAYB" respectively.

DSA Python

# Your code here

Hint

Use double quotes to assign the exact strings to string1 and string2.

2

Create the LCS matrix

Create a 2D list called lcs_matrix with dimensions len(string1) + 1 rows and len(string2) + 1 columns, initialized with zeros.

DSA Python

string1 = "AGGTAB"
string2 = "GXTXAYB"
# Your code here

Hint

Use a list comprehension to create a matrix filled with zeros.

3

Fill the LCS matrix using nested loops

Use nested for loops with variables i and j to iterate over range(1, len(string1) + 1) and range(1, len(string2) + 1) respectively. Inside the loops, if string1[i-1] == string2[j-1], set lcs_matrix[i][j] = lcs_matrix[i-1][j-1] + 1. Otherwise, set lcs_matrix[i][j] = max(lcs_matrix[i-1][j], lcs_matrix[i][j-1]).

DSA Python

string1 = "AGGTAB"
string2 = "GXTXAYB"
lcs_matrix = [[0] * (len(string2) + 1) for _ in range(len(string1) + 1)]
# Your code here

Hint

Use two loops to fill the matrix row by row. Compare characters at i-1 and j-1 positions.

4

Print the length of the longest common subsequence

Print the value at lcs_matrix[len(string1)][len(string2)] which represents the length of the longest common subsequence.

DSA Python

string1 = "AGGTAB"
string2 = "GXTXAYB"
lcs_matrix = [[0] * (len(string2) + 1) for _ in range(len(string1) + 1)]

for i in range(1, len(string1) + 1):
    for j in range(1, len(string2) + 1):
        if string1[i-1] == string2[j-1]:
            lcs_matrix[i][j] = lcs_matrix[i-1][j-1] + 1
        else:
            lcs_matrix[i][j] = max(lcs_matrix[i-1][j], lcs_matrix[i][j-1])

# Your code here

Hint

The bottom-right cell of the matrix holds the final LCS length.

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