Longest Common Subsequence (LCS)

#How does it work?

A subsequence is what you get by deleting some elements of a sequence and keeping the rest in order; the letters don't have to be adjacent. The longest common subsequence (LCS) of ABCBDAB and BDCABA is BCBA (length 4).

dp[i][j] is the LCS length of X's first i letters and Y's first j letters. If the last letters match, that letter joins the LCS: dp[i][j] = dp[i − 1][j − 1] + 1. If not, one of the two letters is left out and the better option wins: max(dp[i − 1][j], dp[i][j − 1]).

Once the table is full, walking back from the bottom right recovers the subsequence itself: on equal letters go diagonally up-left and add the letter, otherwise move to the larger neighbour.

#Try it yourself

#Step by step

1. 01Set the first row and column to 0: an empty string shares nothing.
2. 02For each i, j: if X[i] = Y[j], dp[i][j] = dp[i − 1][j − 1] + 1.
3. 03Otherwise dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]).
4. 04dp[m][n] is the length; read the subsequence by walking back from the bottom right.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def lcs(x: str, y: str) -> str:
    m, n = len(x), len(y)
    # dp[i][j] = LCS length of x[:i] and y[:j]; row 0 and column 0 stay 0.
    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])
    # Walk back from the bottom right (up on ties).
    out, i, j = [], m, n
    while i > 0 and j > 0:
        if x[i - 1] == y[j - 1]:
            out.append(x[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(out))


result = lcs("ABCBDAB", "BDCABA")
print(len(result))
print(result)

#Complexity

m and n are the lengths of the words; each cell is filled in constant time. If only the length is needed, two rows are enough. Hirschberg's algorithm recovers the subsequence itself with linear memory.

#When to use it?

Tools like diff and git finding the differences between two files, aligning DNA and protein sequences, plagiarism detection and spelling suggestions all build on LCS. Its close relative, edit distance, uses the same table.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Edit Distance