Longest Common Subsequence

Q: What is the time complexity of Longest Common Subsequence?

The table solution runs in O(n × m) time, where n and m are the two lengths: it fills one cell per pair of prefixes. It needs O(n × m) memory for the full table, or O(min(n, m)) with two rows. Plain recursion without a table is exponential.

Q: How do you print the longest common subsequence itself?

Fill the full table, then walk back from dp[n][m] . When the two letters at the current cell match, that letter belongs to the answer: record it and step diagonally up and left. Otherwise step to the neighbor above or to the left that holds the larger value. Reverse the recorded letters at the end. The two row version cannot do this, because it has thrown the earlier rows away.

MediumDynamic programming

+10

You get two strings, text1 and text2. A subsequence of a string keeps some of its letters in their original order and drops the rest; the kept letters do not have to be neighbors. Return the length of the longest string that is a subsequence of both, or 0 if the two strings have no letter in common.

Function

longestCommonSubsequence(text1: string, text2: string) → integer

text1string: the first string
text2string: the second string
Returnsinteger: the length of the longest common subsequence

Constraints

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
Both strings contain only lowercase English letters.

Examples

Input: text1 = "stone"text2 = "longest"
Output: 3
Explanation: o, n, e appear in this order in both words, so one is a common subsequence of length 3. In longest the letters s and t come last, while in stone they come first, so a common subsequence that uses them can only be st, which is shorter.

Input: text1 = "pear"text2 = "reap"
Output: 2
Explanation: ea appears in both words. The p and the r sit on opposite sides of ea in the two words, so neither can join it, and the answer is 2.

+19 hidden tests on Submit

Follow-up

Can you return one longest common subsequence itself, not only its length?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Matching letters greedily does not work. A letter can match many places in the other string, and the first match can block better ones: pairing the c of cab with the c at the end of abc leaves nothing for a and b, while skipping it finds ab. The idea that cracks it is that the answer for two prefixes depends only on the answers for slightly shorter prefixes. A table of (n+1) × (m+1) numbers solves every pair once, and since each row reads only the row above, two rows are enough.

Compare first letters with recursion

Correct, but does not finish on the largest tests

Intuition

Let lcs(i, j) be the answer for the suffixes text1[i:] and text2[j:]. Look at their first letters. If they are equal, pair them: a longest common subsequence that does not use this pair can swap its first pair for this one without getting shorter. So the answer is 1 + lcs(i+1, j+1).

If the letters differ, they cannot both be used, since each could only be matched with a later letter of the other string, and the pairs would cross. So one of them can be dropped: the answer is max(lcs(i+1, j), lcs(i, j+1)). When either suffix is empty, nothing is in common and the answer is 0.

It is slow because every mismatch starts two calls. If the strings share no letter, every call mismatches until one string runs out, and the number of calls grows like the number of ways to interleave the two strings. For two strings of 20 letters that is about 2.8 × 10^11 calls; the large tests have 1000 letters each. Yet there are only (n+1) × (m+1) different pairs (i, j), so almost every call repeats an earlier one.

Algorithm

Write lcs(i, j) for the suffixes starting at i and j.
If i or j is past the end of its string, return 0.
If text1[i] == text2[j], return 1 + lcs(i+1, j+1).
Otherwise return max(lcs(i+1, j), lcs(i, j+1)).
The answer is lcs(0, 0).

def longestCommonSubsequence(text1, text2):
    def lcs(i, j):
        # The longest common subsequence of text1[i:] and text2[j:]
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))

    return lcs(0, 0)

Fill a table of prefixes

Intuition

State. Let dp[i][j] be the longest common subsequence of the first i letters of text1 and the first j letters of text2. Working with prefixes lets index 0 mean an empty string.

Recurrence. Compare the last letters of the two prefixes, text1[i-1] and text2[j-1]. If they are equal, pair them: dp[i][j] = dp[i-1][j-1] + 1. If not, drop one of them: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). This is the same reasoning as the recursion, read from the end. Base case: row 0 and column 0 are 0, because an empty prefix has nothing in common with anything. Order: every cell reads the cell above, the cell to its left and the one diagonally up and left, so filling row by row, left to right, always finds them ready. The answer is dp[n][m].

For pear and reap the row for pea is [0, 0, 1, 2, 2]. Its cell for rea is 2 because a matches a, so it is the cell for pe and re, 1, plus one. The last cell, pear against reap, compares r with p, which differ, and takes the larger of its two neighbors, 2.

The table has (n+1) × (m+1) cells and each takes constant work: about 10^6 steps for two strings of 1000 letters. A memoized version of the recursion fills the same cells, but it recurses up to n + m calls deep, which overflows the default call stack in languages such as Python.

Algorithm

Create a table dp of (n+1) × (m+1) zeros.
For i from 1 to n and j from 1 to m, compare text1[i-1] with text2[j-1].
On a match, set dp[i][j] = dp[i-1][j-1] + 1.
Otherwise set dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Return dp[n][m].

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    # dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
    # Row 0 and column 0 stay 0: an empty prefix has nothing in common.
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Keep only two rows

Intuition

Row i of the table reads only row i-1 and its own earlier cells. Once a row is done, every row above it is never read again. So keep two arrays, prev for the finished row and cur for the row being filled, and swap them after each row. The recurrence and the order stay exactly the same.

A common subsequence of two strings does not care which string is first, so you can swap them and let the rows run along the shorter one. Each row then holds min(n, m) + 1 numbers: 1001 instead of a million cells for the largest inputs, with the same 10^6 steps of work.

The first entry of every row stands for an empty prefix of the shorter string, so it must stay 0. The answer is the last entry of the last finished row.

Algorithm

If text2 is longer than text1, swap them.
Create prev and cur, each m + 1 zeros, where m is the shorter length.
For each letter of text1, fill cur[1..m] with the same rule as the table, reading prev for the row above.
Swap prev and cur.
Return prev[m].

def longestCommonSubsequence(text1, text2):
    if len(text2) > len(text1):
        text1, text2 = text2, text1  # keep the rows as short as the shorter string
    m = len(text2)
    # prev[j]: the answer for the previous prefix of text1 and text2[:j]
    prev = [0] * (m + 1)
    for ch in text1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == text2[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

Pitfalls and edge cases

The recurrence is short, and most bugs are off by one or add a match in the wrong place.

Mixing table indexes with string indexes. Cell dp[i][j] compares text1[i-1] with text2[j-1], because row 0 is the empty prefix.
On a match, adding one to max(dp[i-1][j], dp[i][j-1]) instead of to dp[i-1][j-1]. That can use one letter twice: aa against a would return 2 instead of 1.
Matching greedily with two pointers. cab against abc pairs the two c letters and returns 1, while ab gives 2.
Writing into the row you are still reading from. With two rows, every value from the row above must come from prev, and cur[0] must stay 0.
Solving longest common substring by mistake. A subsequence may skip letters; a substring may not.
Memoizing with recursion on 1000-letter strings. The call depth reaches 2000, past Python's default limit of 1000.

Frequently asked questions4

What is the time complexity of Longest Common Subsequence?

The table solution runs in O(n × m) time, where n and m are the two lengths: it fills one cell per pair of prefixes. It needs O(n × m) memory for the full table, or O(min(n, m)) with two rows. Plain recursion without a table is exponential.

What is the difference between longest common subsequence and longest common substring?

A subsequence may skip letters as long as the order is kept, while a substring is a block of neighboring letters. For stone and longest the longest common subsequence is one (3), but the longest common substring is on (2). The substring version uses a similar table, but a mismatch resets the cell to 0 instead of copying a neighbor.

How do you print the longest common subsequence itself?

Fill the full table, then walk back from dp[n][m]. When the two letters at the current cell match, that letter belongs to the answer: record it and step diagonally up and left. Otherwise step to the neighbor above or to the left that holds the larger value. Reverse the recorded letters at the end. The two row version cannot do this, because it has thrown the earlier rows away.

How is LCS related to diff tools and edit distance?

A diff between two versions of a file finds the longest common subsequence of their lines; every line outside it is shown as added or removed. In the same way, the fewest insertions and deletions that turn one string into the other is n + m - 2 × LCS. Edit distance also allows replacing a letter, so it uses its own table with a third choice per cell.

Python

def longestCommonSubsequence(text1, text2):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

text1 = "stone"
text2 = "longest"

Expected

Longest Common Subsequence

Function

Constraints

Examples

Hints

Solution

Compare first letters with recursion

Fill a table of prefixes

Keep only two rows

Pitfalls and edge cases

Frequently asked questions4

Similar problems