Longest Common Subsequence in DSA Python

Mental Model

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

Analogy: Imagine two friends telling stories with some common events. The longest common subsequence is like the longest list of shared events they both mention in the same order, even if they skip some details.

String1: A B C D G H
String2: A E D F H R

LCS: A   D     H

Visual: Characters aligned where they match in order, skipping others.

Dry Run Walkthrough

Input: String1: "ABCDGH", String2: "AEDFHR"

Goal: Find the longest common subsequence between the two strings.

Step 1: Initialize a 2D table with zeros for lengths of subsequences.

Table rows for 'ABCDGH' + 1, columns for 'AEDFHR' + 1, all zeros initially.

Why: We need a base to build subsequence lengths from empty prefixes.

Step 2: Compare first characters 'A' and 'A', they match, set table[1][1] = 1.

Table[1][1] = 1, rest zeros.

Why: Matching characters increase subsequence length by 1.

Step 3: Compare 'B' and 'E', no match, take max from left or top cell.

Table[2][2] = max(table[1][2], table[2][1]) = 1.

Why: No match means subsequence length stays as max of previous.

Step 4: Continue filling table comparing all characters, updating lengths.

Partial table filled with lengths showing longest subsequence lengths at each prefix.

Why: Dynamic programming builds solutions from smaller problems.

Step 5: Final table cell table[6][6] = 3, longest subsequence length is 3.

Table completed, max length 3 at bottom-right.

Why: This cell represents the full strings' longest common subsequence length.

Step 6: Trace back from table[6][6] to find the subsequence characters 'A', 'D', 'H'.

LCS sequence found: 'A' -> 'D' -> 'H'.

Why: Backtracking recovers the actual subsequence from the length table.

Result:

Longest Common Subsequence length = 3
Sequence: A -> D -> H

Annotated Code

DSA Python

class LCS:
    def longest_common_subsequence(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                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 to find the subsequence
        i, j = m, n
        lcs_chars = []
        while i > 0 and j > 0:
            if s1[i - 1] == s2[j - 1]:
                lcs_chars.append(s1[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1

        return ''.join(reversed(lcs_chars))


if __name__ == '__main__':
    s1 = "ABCDGH"
    s2 = "AEDFHR"
    lcs_solver = LCS()
    result = lcs_solver.longest_common_subsequence(s1, s2)
    print(f"Longest Common Subsequence length = {len(result)}")
    print(f"Sequence: {' -> '.join(result)}")

for i in range(1, m + 1): for j in range(1, n + 1):

iterate over all prefixes of both strings to build dp table

if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1

characters match, extend subsequence length by 1

else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

no match, take max subsequence length from previous prefixes

while i > 0 and j > 0:

backtrack from bottom-right to find subsequence characters

if s1[i - 1] == s2[j - 1]: lcs_chars.append(s1[i - 1]) i -= 1 j -= 1

match found, add character and move diagonally up-left

elif dp[i - 1][j] > dp[i][j - 1]: i -= 1 else: j -= 1

move in direction of larger dp value to continue backtracking

Output

Longest Common Subsequence length = 3

Sequence: A -> D -> H

Complexity Analysis

Time: O(m*n) because we fill a table of size m by n once

Space: O(m*n) because we store subsequence lengths for all prefix pairs

vs Alternative: Naive recursive approach is exponential due to repeated subproblems; DP reduces it to polynomial time.

Edge Cases

One or both strings empty

Returns empty subsequence with length 0

DSA Python

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

No common characters

Returns empty subsequence with length 0

DSA Python

else:
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

Strings are identical

Returns the entire string as subsequence

DSA Python

if s1[i - 1] == s2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1] + 1

When to Use This Pattern

When you need to find the longest sequence common to two sequences in order, use the Longest Common Subsequence pattern because it efficiently finds shared order without requiring contiguity.

Common Mistakes

Mistake: Not initializing the dp table with an extra row and column for empty prefixes
Fix: Initialize dp with size (m+1) x (n+1) to handle empty string cases correctly

Mistake: Appending characters during backtracking without reversing the result
Fix: Reverse the collected characters after backtracking to get correct order

Summary

Finds the longest sequence of characters common to both strings in order.

Use when comparing two sequences to find shared ordered elements, like diff tools or DNA analysis.

Build a table of subsequence lengths and backtrack to recover the sequence.

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