Longest Common Subsequence

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

The table solution runs in O(n × m) time, 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.

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 common, length 3. The letters s and t come last in longest but first in stone, so using them gives at most st.

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.

Follow-up

Can you return one longest common subsequence itself, along with its length?

Hints

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

0 of 3 opened

Solution

Greedy matching fails: pairing the c of cab with the last c of abc leaves nothing for a and b; skipping it finds ab. The answer for two prefixes depends on the answers for shorter prefixes, so a (n+1) × (m+1) table solves every pair once. Each row reads only the row above, so 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:]. If their first letters are equal, pair them: a longest common subsequence that skips 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, because their partners would make the pairs cross. So one of them can be dropped: max(lcs(i+1, j), lcs(i, j+1)). An empty suffix gives 0.

Every mismatch starts two calls. Two 20-letter strings with no common letter already take about 2.8 × 10^11 calls, 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

Let dp[i][j] be the answer for the first i letters of text1 and the first j letters of text2, so index 0 means an empty prefix and row 0 and column 0 are 0. Compare the last letters of the two prefixes, text1[i-1] and text2[j-1]: equal letters pair up, dp[i-1][j-1] + 1; different letters drop one of them, max(dp[i-1][j], dp[i][j-1]). It is the recursion read from the end.

Each cell reads the cells above, to the left and diagonally up and left, so filling row by row, left to right, always finds them ready. For pear and reap the row for pea is [0, 0, 1, 2, 2]; its cell for rea is 2 because a matches a, adding one to the cell for pe and re.

Two strings of 1000 letters take about 10^6 constant-time steps.

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

Once a row is done, the rows above it are never read again. Keep prev for the finished row and cur for the row being filled, and swap them after each row. The recurrence and the order stay the same.

The answer does not depend on which string comes first, so 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.

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

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.
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.
Memoizing the recursion in Python on 1000-letter strings. The call depth reaches 2000, past the default limit of 1000.

Frequently asked questions3

What is the time complexity of Longest Common Subsequence?

The table solution runs in O(n × m) time, 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; 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 table resets a cell to 0 on a mismatch instead of copying a neighbor.

How is LCS related to diff tools and edit distance?

A diff between two versions of a file keeps the longest common subsequence of their lines and shows every other line as added or removed. 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 needs its own table.

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

Test #1

Test #2

Test #3

Arguments

text1 = "stone"
text2 = "longest"

Expected Output

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 questions3

Similar problems