How to Get Longest Common Subsequence in Python

1. Use the Naive Method to Find Longest Common Subsequence in Python
2. Use Dynamic Programming to Find Longest Common Subsequence in Python

A subsequence is a sequence obtained from the given sequences after removing some or no characters without changing the order of the remaining characters. The longest common subsequence means the longest subsequence common to all the given sequences.

This tutorial will teach you to find the length of the longest common subsequence between two sequences in Python.

Use the Naive Method to Find Longest Common Subsequence in Python

Consider we have two sequences: S1 and S2, where:

S1 = QEREW

S2 = QWRE

Here, the common subsequences are QE, QW, QR, QRE, and RE. Among these, the longest common subsequence is QRE, and its length is 3.

Now, let’s look at the Python solution to print the length of the longest common subsequence.

Code:

def LCS(S1, S2, x, y):

    if x == 0 or y == 0:
        return 0

    if S1[x - 1] == S2[y - 1]:
        return LCS(S1, S2, x - 1, y - 1) + 1

    return max(LCS(S1, S2, x, y - 1), LCS(S1, S2, x - 1, y))


S1 = "QEREW"
S2 = "QWRE"
x = len(S1)
y = len(S2)
print("Length of LCS is", LCS(S1, S2, x, y))

Output:

Length of LCS is 3

This method is a recursive approach to solving the LCS problem in Python. It checks for all possible subsequences of given sequences and finds the longest common subsequence.

Use Dynamic Programming to Find Longest Common Subsequence in Python

Dynamic programming is the optimization of the plain recursion method. As we can see, there are overlapping sub-problems in the recursive approach, with many repeated function calls.

The dynamic approach saves the result of each function call in an array so it can be used when needed. As a result, it reduces the number of function calls.

Code:

def LCS(S1, S2, m, n):
    R = [[None] * (n + 1) for i in range(m + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                R[i][j] = 0
            elif S1[i - 1] == S2[j - 1]:
                R[i][j] = R[i - 1][j - 1] + 1
            else:
                R[i][j] = max(R[i - 1][j], R[i][j - 1])

    return R[m][n]


S1 = "QEREW"
S2 = "QWRE"
m = len(S1)
n = len(S2)
print("Length of LCS is", LCS(S1, S2, m, n))

Output:

Length of LCS is 3

This method is faster and more efficient as it has the time complexity of O(mn).