Python programs / Dynamic programming / Longest common subsequence

Python Program for the Longest Common Subsequence (LCS)

Advanced Dynamic programming Time O(m × n) Space O(m × n)

Finds the longest run of letters that appears in the same order, not always side by side, in both of two strings, with a table.

A subsequence of a string is what's left after deleting some of its letters, keeping the rest in order: ONE is a subsequence of LONGEST (LONGEST). The longest common subsequence (LCS) of two strings is the longest string that's a subsequence of both: for STONE and LONGEST it's ONE, 3 letters. Unlike a substring, its letters don't have to sit next to each other. Tools like diff use it to find the lines two files share, and biologists to compare DNA. Trying every subsequence of a 20-letter string means over a million of them, so the program fills in a table of the LCS lengths of shorter pieces instead.

Program

def lcs(a, b):
    """The longest common subsequence of the strings a and b."""
    # length[i][j]: the LCS length of a[:i] and b[:j]
    length = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                length[i][j] = length[i - 1][j - 1] + 1
            else:
                length[i][j] = max(length[i - 1][j], length[i][j - 1])

    # Walk back from the last cell to read the letters
    letters = []
    i, j = len(a), len(b)
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            letters.append(a[i - 1])
            i -= 1
            j -= 1
        elif length[i - 1][j] >= length[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(letters))


result = lcs("STONE", "LONGEST")
print("Longest common subsequence:", result)
print("Its length:", len(result))

Open in the editor Download longest_common_subsequence.py

Output

Longest common subsequence: ONE
Its length: 3

How it works

  1. length is a table with a row for each start of a (from no letters to all of them) and a column for each start of b. length[i][j] will be the LCS length of the first i letters of a and the first j of b. Row 0 and column 0, where one string is empty, stay 0.
  2. The table is filled row by row. When the last letters of the two pieces match (a[i - 1], as strings count from 0), that letter can end the subsequence, so the length is one more than without both letters: the cell up and to the left.
  3. When they don't match, at least one of the two letters isn't in the subsequence, so the length is the larger of dropping a's letter (the cell above) and dropping b's (the cell to the left).
  4. The bottom-right cell holds the LCS length. To find its letters, the program starts there, with an empty list.
  5. Where the two letters match, that letter is in the LCS: it's collected, and the walk moves up and to the left.
  6. Otherwise the walk moves to the neighbour the cell's value came from: up if the cell above is at least as large, left if not.
  7. The letters were collected from the end, so they're reversed and joined into a string.
  8. The program finds the LCS of STONE and LONGEST, and prints it and its length.

The table for STONE (down) and LONGEST (across), with the matches the walk back collects in bold:

L O N G E S T
0 0 0 0 0 0 0 0
S 0 0 0 0 0 0 1 1
T 0 0 0 0 0 0 1 2
O 0 0 1 1 1 1 1 2
N 0 0 1 2 2 2 2 2
E 0 0 1 2 2 3 3 3

The walk starts at the bottom-right 3, moves left past T and S to the E, then collects E, N and O on its way up and to the left. The 2 in the T row comes from ST, which starts STONE and ends LONGEST, but it loses to ONE.

Time and space complexity

TimeO(m × n)
Extra spaceO(m × n)

The table has (m + 1) × (n + 1) cells for strings of m and n letters, and each one is filled with a single comparison, so the time and the space are both O(m × n). The walk back takes at most m + n steps. When only the length is wanted, two rows are enough (below), which takes O(n) space; finding the letters needs the whole table.

Other ways to write it

With recursion and lru_cache

Top-down: compare the first letters of what's left of each string. If they match, that letter is in the LCS; if not, try dropping one or the other. lru_cache, a decorator, remembers the answer for each (i, j), so each is worked out once. This version gives the length.

from functools import lru_cache

def lcs_length(a, b):
    @lru_cache(maxsize=None)
    def solve(i, j):
        if i == len(a) or j == len(b):
            return 0
        if a[i] == b[j]:
            return solve(i + 1, j + 1) + 1
        return max(solve(i + 1, j), solve(i, j + 1))

    return solve(0, 0)

print(lcs_length("STONE", "LONGEST"))

The length with two rows

Each row reads only the row above it, so when only the length is wanted, the program can keep two rows instead of the whole table.

def lcs_length(a, b):
    previous = [0] * (len(b) + 1)
    for letter in a:
        current = [0]
        for j in range(1, len(b) + 1):
            if letter == b[j - 1]:
                current.append(previous[j - 1] + 1)
            else:
                current.append(max(previous[j], current[j - 1]))
        previous = current
    return previous[-1]

print(lcs_length("HUMAN", "CHIMPANZEE"))

Try it yourself

  • Find the LCS of "HUMAN" and "CHIMPANZEE". It's HMAN.
  • Try two strings with no letter in common, such as "ABC" and "XYZ". The LCS is the empty string, of length 0.
  • "ABCBDAB" and "BDCABA" have more than one LCS of length 4. The program finds BCBA; change the >= in the walk back to > and it finds BDAB.
  • Compare lists of words instead of strings, as diff compares lines: return letters[::-1] instead of joining them, and call lcs("the cat sat on the mat".split(), "the dog sat on a mat".split()). The result is ['the', 'sat', 'on', 'mat'].

More dynamic programming programs

Share this program