Python Program to Find the Longest Common Subsequence

The Longest Common Subsequence (LCS) problem asks: given two strings, what's the longest sequence of characters that appears in both, in the same relative order, but not necessarily contiguously? For example, the LCS of "ABCBDAB" and "BDCABA" is "BCBA" (length 4). LCS shows up constantly in real tools — it's the core of the "diff" algorithm used by Git to show what changed between two file versions, and it's a staple dynamic programming interview question.

A brute-force solution that tries every possible subsequence is exponential — O(2^n) — so this post uses dynamic programming, building up a 2D table of answers to smaller subproblems.

Python Program to Find the Longest Common Subsequence

def longest_common_subsequence(a, b):
    m, n = len(a), len(b)
    # dp[i][j] = length of the LCS of a[:i] and b[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Reconstruct the actual subsequence by walking the table backward
    i, j = m, n
    subsequence = []
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            subsequence.append(a[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return dp[m][n], "".join(reversed(subsequence))


a = "ABCBDAB"
b = "BDCABA"
length, sequence = longest_common_subsequence(a, b)
print(f"LCS length: {length}")
print(f"LCS: {sequence}")

Output:

LCS length: 4
LCS: BCBA

The recurrence is the heart of this: if the current characters a[i-1] and b[j-1] match, they must be part of the LCS, so we add 1 to the diagonal value dp[i-1][j-1]; otherwise, we take the best result from either dropping a character from a or from b. Filling the table takes O(m × n) time and space, where m and n are the two string lengths — a huge improvement over the exponential brute-force approach. The same table-filling pattern — build up answers to smaller subproblems using a simple loop instead of re-solving things from scratch — is reused in related problems like the Longest Increasing Subsequence and edit distance.

---