Mastering the Longest Common Subsequence Algorithm in Python • Llego.dev

The longest common subsequence (LCS) problem is a classic computer science problem with applications in fields like bioinformatics, natural language processing, and data analysis. The goal is to find the longest subsequence that is common between two given sequences. This how-to guide will provide a comprehensive walkthrough on solving the LCS problem in Python, including finding the length of the LCS and reconstructing the actual LCS string.

Overview of the Longest Common Subsequence Problem

Formally, given two sequences X and Y, the longest common subsequence problem aims to find the longest sequence Z that is a subsequence of both X and Y.

A subsequence does not need to be contiguous - it can be obtained by deleting zero or more elements from the original sequence without changing the order of the remaining elements.

For example, let:

X = "AGGTAB"
Y = "GXTXAYB"

One of the LCS is “GTAB” - it is the longest sequence present in both X and Y while preserving the order of elements. Other possible LCS are “GTB”, “GAB”, etc.

The LCS problem has many real-world applications:

Bioinformatics: Finding similarities between DNA sequences or proteins. The LCS can identify conserved regions and analyzes genetic connections.
Text Processing: Used in spell checkers, plagiarism detection, natural language processing, etc. to find similarities between textual documents.
Data Analysis: Analyzing data versions, temporal changes, data lineage, etc. by finding the commonalities between data sets.
Computer Science: Used in diff utilities like git diff to highlight changes between code versions or files. Also has applications in file comparison, data reconciliation, etc.

The LCS problem can be solved using dynamic programming and memoization. The overall algorithm involves building a 2D matrix to store lengths of LCSes of substring pairs and using it to reconstruct the actual LCS.

Finding the Length of the Longest Common Subsequence

Let’s break down the steps to find just the length of the LCS between two strings X and Y:

1. Initialize the LCS matrix

We will build an (m+1 x n+1) matrix lcs_mat to store the LCS lengths, where m and n are the lengths of sequences X and Y respectively. We add 1 to the dimensions to handle base cases where one or both sequences are empty.

Initialize all elements of lcs_mat to 0.

X = "AGGTAB"
Y = "GXTXAYB"

m = len(X)
n = len(Y)

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

This initializes a 2D array with m+1 rows and n+1 columns filled with 0s.

2. Build the LCS matrix in a bottom-up manner

We will now progressively build up the LCS matrix by comparing characters of X and Y:

for i in range(m):
    for j in range(n):
        if X[i] == Y[j]:
            lcs_mat[i + 1][j + 1] = lcs_mat[i][j] + 1
        else:
            lcs_mat[i + 1][j + 1] = max(lcs_mat[i + 1][j], lcs_mat[i][j + 1])

We traverse the strings character by character using nested loops.
If the current characters X[i] and Y[j] match, the length of the LCS ending at these positions is one more than the LCS of the prefixes X[:i] and Y[:j], which is stored in lcs_mat[i][j].
If the characters do not match, the length of the LCS is the maximum of the LCS ending at X[:i] and Y[:j+1] (represented by lcs_mat[i][j+1]) or the LCS ending at X[:i+1] and Y[:j] (represented by lcs_mat[i+1][j]).

This builds up the length matrix incrementally based on the LCS values of previous prefixes.

3. The final LCS length is computed

The length of the LCS between X and Y will be the value in the bottom-right cell of lcs_mat:

return lcs_mat[m][n]

This will give us the maximum length of the possible LCS between the two strings.

Let’s see a complete example to find just the LCS length:

def lcs_length(X, Y):
    m = len(X)
    n = len(Y)

    # initialize LCS matrix
    lcs_mat = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

    # build the matrix in bottom-up manner
    for i in range(m):
        for j in range(n):
            if X[i] == Y[j]:
                lcs_mat[i + 1][j + 1] = lcs_mat[i][j] + 1
            else:
                lcs_mat[i + 1][j + 1] = max(lcs_mat[i + 1][j], lcs_mat[i][j + 1])

    # LCS will be the last element in the matrix
    return lcs_mat[m][n]

X = "AGGTAB"
Y = "GXTXAYB"
print("Length of LCS is:", lcs_length(X, Y))

This prints Length of LCS is: 4 as the length of the LCS between strings “AGGTAB” and “GXTXAYB”.

The time complexity of this algorithm is O(m x n) as we iterate through the entire LCS matrix of size (m+1) x (n+1). The space complexity is also O(m x n) due to the matrix.

Reconstructing the Longest Common Subsequence

In many cases, finding just the LCS length is not sufficient - we also need to reconstruct the actual longest common subsequence between X and Y.

This can be done by tracing back through the lcs_mat to identify the path that led to the final LCS length.

The steps are:

1. Utilize the LCS matrix (already computed)

We reuse the lcs_mat computed in the previous section.

# X and Y sequences
X = "AGGTAB"
Y = "GXTXAYB"

m = len(X)
n = len(Y)

# initialize matrices
lcs_mat = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

# build matrix (same as before)
for i in range(m):
    for j in range(n):
        if X[i] == Y[j]:
            lcs_mat[i + 1][j + 1] = lcs_mat[i][j] + 1
        else:
            lcs_mat[i + 1][j + 1] = max(lcs_mat[i + 1][j], lcs_mat[i][j + 1])

2. Traceback from the end cell

We start from the bottom-right cell of lcs_mat (index [m][n]) and move backwards, reconstructing the LCS.

i = m
j = n
lcs = ""

while i > 0 and j > 0:
    if X[i - 1] == Y[j - 1]:
        lcs += X[i - 1]
        i -= 1
        j -= 1
    elif lcs_mat[i][j - 1] > lcs_mat[i - 1][j]:
        j -= 1
    else:
        i -= 1

We initialize i and j to m and n, respectively.
If X[i-1] and Y[j-1] are equal, it means this character is part of the LCS. We prepend it to the lcs string and move diagonally up-left (i -= 1, j -= 1).
If the characters are not equal, we move to the cell that has the larger LCS value – either the cell above (lcs_mat[i-1][j]) or the cell to the left (lcs_mat[i][j-1]). This indicates which subproblem contributed to the current LCS length.

3. Return the reconstructed LCS

The lcs string is built in reverse order, so we need to reverse it to get the correct LCS.

return lcs[::-1]

Here is the full program:

def lcs(X, Y):
    m = len(X)
    n = len(Y)

    # initialize matrices
    lcs_mat = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

    # build matrix in bottom-up manner
    for i in range(m):
        for j in range(n):
            if X[i] == Y[j]:
                lcs_mat[i + 1][j + 1] = lcs_mat[i][j] + 1
            else:
                lcs_mat[i + 1][j + 1] = max(lcs_mat[i + 1][j], lcs_mat[i][j + 1])

    # traceback to find LCS
    i = m
    j = n
    lcs = ""

    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            lcs += X[i - 1]
            i -= 1
            j -= 1
        elif lcs_mat[i][j - 1] > lcs_mat[i - 1][j]:
            j -= 1
        else:
            i -= 1

    return lcs[::-1]

X = "AGGTAB"
Y = "GXTXAYB"

print("LCS is", lcs(X, Y))

This dynamically generates the LCS length matrix and uses it to reconstruct the longest common subsequence “GTAB”.

The overall time and space complexity remains O(m x n). This provides an optimal quadratic solution for the LCS problem.

Further Improvements

Some refinements can be made to the above algorithm:

Space Optimization: Maintain only the previous row of lcs_mat instead of the entire matrix to reduce space complexity to O(min(m, n)). This is possible because the current row only depends on the previous row. However, this optimization makes reconstructing the actual LCS more difficult.
Memoization: While the iterative dynamic programming approach used here is generally preferred for LCS due to its straightforward implementation, a recursive solution with memoization can also be used.
Scoring: For applications like bioinformatics, you can assign scores to matches and mismatches to find the alignment with the highest score, which is a generalization of the LCS problem.
All LCSs: If you need to find all possible longest common subsequences, the traceback step can be modified to explore all paths that lead to the maximum LCS length.
Multiple Sequences: The LCS algorithm can be extended to handle more than two sequences, although the complexity increases.

Applications of LCS in Python

The LCS algorithm has many applications for Python developers:

Version control - Finding differences between code versions to highlight changes. The diff utility internally uses concepts related to LCS.
Text comparisons - Plagiarism detection, spell checking by finding commonality between texts. Useful in NLP tasks.
Bioinformatics - DNA or protein sequence alignment to find conserved regions and mutations. Helps analyze evolutionary connections. Biopython library provides tools for sequence alignment.
Data analysis - Data integration, data lineage analysis, temporal change detection by finding commonalities between data sets.
Security - Analyzing similarities between malware variants or intrusion patterns by computing LCS.
Compression - Identifying and encoding common substrings can aid in data compression techniques.
Education - A valuable example for teaching dynamic programming, algorithm design, and problem-solving techniques.

Conclusion

This guide covered a step-by-step process to find the longest common subsequence between two strings in Python. We looked at:

The LCS problem definition and its wide range of real-world applications.
A dynamic programming solution to incrementally build the LCS matrix for finding the length.
A traceback technique to reconstruct the actual LCS using the computed matrix.
Ideas for further optimizing the algorithm and exploring variations.
Usage of LCS in diverse domains relevant to Python development and beyond.

The LCS problem is a foundational computer science challenge that frequently appears in technical interviews. I hope this comprehensive Python guide provided both conceptual clarity and practical, implementable code samples to help master this classic algorithm.