Longest Common Subsequence

Analogy categoryAnalogies

Introduction

The Longest Common Subsequence (LCS) problem asks: given two sequences (typically strings), find the length (and optionally the content) of the longest subsequence common to both, where a subsequence preserves relative order but need not be contiguous. LCS underlies real tools like diff utilities and DNA sequence comparison. It has optimal substructure — the LCS of two strings can be built from the LCS of their prefixes — and overlapping subproblems, since the LCS of a given prefix pair (i, j) is asked for repeatedly across different comparison paths, so it is solved with a 2D DP table.

🏏

Cricket analogy: Finding the longest sequence of shot types that appear, in order but not necessarily back-to-back, in both an opener's innings and a middle-order batsman's innings is the LCS problem; because the same prefix-pair of overs gets compared repeatedly across different match analyses, a 2D table is used.

Approach/Syntax

python

# dp[i][j] = length of LCS of text1[:i] and text2[:j]
# Recurrence:
#   dp[0][j] = dp[i][0] = 0                              (empty prefix -> LCS length 0)
#   dp[i][j] = dp[i-1][j-1] + 1                           if text1[i-1] == text2[j-1]
#   dp[i][j] = max(dp[i-1][j], dp[i][j-1])                otherwise

def lcs_length(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[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

Explanation

dp[i][j] holds the LCS length between the first i characters of text1 and the first j characters of text2. If the last characters text1[i-1] and text2[j-1] match, that character must be part of the LCS, so we extend the LCS of the two shorter prefixes (dp[i-1][j-1]) by 1. If they don't match, the LCS must come from either dropping the last character of text1 or dropping the last character of text2, so we take the better of dp[i-1][j] and dp[i][j-1]. Every cell only depends on cells above, to the left, or diagonally above-left, so filling the table row by row (or column by column) guarantees each needed subproblem is already solved.

🏏

Cricket analogy: If the last shot in both innings' sequences matches (say, both end in a six), the table cell extends the diagonal value by one; if they don't match, the cell takes the better of dropping the last shot from either innings, filling the scorecard grid row by row.

Example

code

def lcs_with_string(text1, text2):
    m, n = len(text1), len(text2)
    dp = lcs_length(text1, text2)

    # Reconstruct the actual LCS string by walking backward
    i, j = m, n
    result = []
    while i > 0 and j > 0:
        if text1[i - 1] == text2[j - 1]:
            result.append(text1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    result.reverse()
    return dp[m][n], "".join(result)

text1, text2 = "ABCBDAB", "BDCABA"
length, subsequence = lcs_with_string(text1, text2)
print(f"LCS length: {length}")          # LCS length: 4
print(f"LCS string: {subsequence}")     # LCS string: BCBA (or another valid LCS of length 4)

Output/Complexity

For text1='ABCBDAB' and text2='BDCABA', the algorithm outputs 'LCS length: 4' with a matching subsequence such as 'BCBA' (there can be multiple valid LCS strings of the same maximum length). Filling the m x n DP table takes O(m * n) time and O(m * n) space, where m and n are the lengths of the two input strings. Backward reconstruction of the actual subsequence adds only O(m + n) extra time since it walks at most one step in each direction per iteration. Space can be reduced to O(min(m, n)) if only the length (not the actual subsequence) is required, by keeping just two rows of the table at a time.

🏏

Cricket analogy: Comparing two innings' shot sequences of 7 and 6 shots takes an O(m*n) table fill, say yielding a matching sub-sequence of length 4 like 'four-six-four-six'; tracing back the exact shots costs only O(m+n), and if you only need the length, you can keep just two rows of overs, cutting memory to O(min(m,n)).

Key Takeaways

LCS finds the longest order-preserving (not necessarily contiguous) sequence common to two strings.
The recurrence extends the diagonal by 1 on a character match, otherwise takes the max of dropping one character from either string.
Time and space complexity are both O(m * n) for strings of length m and n.
The actual LCS string is recovered by walking the filled table backward from dp[m][n].
Space can be optimized to O(min(m, n)) when only the length is needed, not the reconstructed string.

Practice what you learned

1. What is the key difference between a subsequence and a substring in the context of LCS?

2. In the LCS recurrence, what happens when text1[i-1] equals text2[j-1]?

3. What is the time and space complexity of the standard LCS DP algorithm for strings of length m and n?

4. When text1[i-1] and text2[j-1] do not match, how is dp[i][j] computed?

Was this page helpful?

0/1 Knapsack Problem

Coin Change Problem

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#LongestCommonSubsequence#Longest#Common#Subsequence#Approach#StudyNotes#SkillVeris