LESSON 427 OF 501 · DYNAMIC PROGRAMMING

Longest Common Subsequence in Python

Practice O(n · m)

You are given two strings text1 and text2. Return the length of their longest common subsequence, or 0 if they have no common subsequence.

A subsequence of a string is what remains after deleting some of its characters, possibly none, without changing the order of the others. For example, "ace" is a subsequence of "abcde", but "aec" is not: the characters must keep their order. A common subsequence of two strings is a subsequence of both of them.

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: "ace" is a subsequence of both strings. text2 has only 3 characters, so no common subsequence can be longer.

Example 2:

Input: text1 = "abcbdab", text2 = "bdcaba"
Output: 4
Explanation: "bcba" is a subsequence of both: b, c, b and a appear in this order in each string. "bdab" works too, and no common subsequence has 5 characters. Only the length is returned.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: No character appears in both strings, so the only common subsequence is the empty one.

Constraints:

1 <= text1.length, text2.length <= 1000
text1 and text2 are made of lowercase English letters only, a to z.

Note:

Your algorithm should run in O(n · m) time and space, where n is the length of text1 and m the length of text2.

Trying every subsequence is far too slow: a string of 1000 characters has 2¹⁰⁰⁰ of them. Solve smaller versions of the problem instead: let dp[i][j] be the length of the longest common subsequence of the first i characters of text1 and the first j characters of text2. The table has (n + 1) × (m + 1) entries. Row 0 and column 0 stand for an empty prefix, which has nothing in common with anything, so they stay 0. The answer is dp[n][m].

Fill the table row by row, so the entries above, to the left and diagonally up-left of dp[i][j] are already known. Look at the last characters of the two prefixes, text1[i - 1] and text2[j - 1]:

When they are equal, dp[i][j] = dp[i - 1][j - 1] + 1. Adding this shared character to the best common subsequence of the two shorter prefixes reaches that length, and nothing does better: removing the last character of any common subsequence leaves a common subsequence of the two shorter prefixes.
When they differ, dp[i][j] is the larger of dp[i - 1][j] and dp[i][j - 1]. A common subsequence can't end with both of them, so it leaves out at least one, and then it is a common subsequence of the prefixes without that character.

The table has (n + 1) × (m + 1) entries, and each one takes a constant amount of work: O(n · m) time and O(n · m) space.
Each row reads only itself and the row above it, so two rows of m + 1 numbers are enough, which brings the space down to O(m). The lesson keeps the whole table, which is easier to follow.

STEP 1 OF 7

Guided

Ctrl + Enter to check