Start learning free

LESSON 533 OF 673 · DYNAMIC PROGRAMMING

Longest Common Subsequence in Python: 2D DP in O(n·m)

Practice O(n · m) Read the full explanation

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 21000 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
    Ctrl + Enter to check

    PYTHON · DYNAMIC PROGRAMMING

    Longest Common Subsequence in Python, explained

    Problem overview

    The method longestCommonSubsequence receives two strings, text1 and text2, and returns the length of their longest common subsequence. A subsequence is what remains after deleting some characters, possibly none, without reordering the rest. "ace" is a subsequence of "abcde", but "aec" is not. A common subsequence is a subsequence of both strings. Only the length is returned, and it is 0 when the strings share no character. Both strings have 1 to 1000 lowercase letters, and the statement asks for O(n · m) time and space.

    For "abcde" and "ace" the answer is 3, from "ace". For "abc" and "def" it is 0.

    Approach: solve every pair of prefixes

    A string of 1000 characters has up to 2 to the power of 1000 subsequences, so comparing them all is out of the question. Instead, solve smaller versions. 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 answer is dp[n][m], where n and m are the string lengths.

    Look at the last characters of the two prefixes, text1[i - 1] and text2[j - 1]:

    • They are equal. Then dp[i][j] = dp[i - 1][j - 1] + 1. Adding the shared character to the best answer for the 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.
    • They differ. A common subsequence can't end with both characters, so it leaves out at least one. Then dp[i][j] is the larger of dp[i - 1][j] (without the last character of text1) and dp[i][j - 1] (without the last character of text2).

    Row 0 and column 0 stand for an empty prefix, which has nothing in common with anything, so they stay 0.

    Step by step

    1. Store the lengths: n = len(text1) and m = len(text2). Both come up often.
    2. Create the table with n + 1 rows, each a new list of m + 1 zeros, using a list comprehension. The extra row and column are the empty prefixes. The name _ says the loop variable isn't used.
    3. Loop i over range(1, n + 1), one row per prefix of text1. Row 0 already holds zeros.
    4. Loop j over range(1, m + 1) inside it. Filling row by row and left to right means the entries above, to the left and diagonally up-left are known when dp[i][j] is computed.
    5. Equal last characters: if text1[i - 1] == text2[j - 1], set dp[i][j] to dp[i - 1][j - 1] + 1. The first i characters end at index i - 1, because the string counts from 0 while the table counts characters.
    6. Different last characters: in the else, set dp[i][j] to max(dp[i - 1][j], dp[i][j - 1]).
    7. Return dp[n][m], the answer for both whole strings.

    The solution in Python

    class Solution:
        def longestCommonSubsequence(self, text1: str, text2: str) -> int:
            n = len(text1)
            m = len(text2)
            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]
    

    For "abcde" and "ace" the finished table has one row per prefix of "abcde", starting with the empty prefix:

    [0, 0, 0, 0]
    [0, 1, 1, 1]
    [0, 1, 1, 1]
    [0, 1, 2, 2]
    [0, 1, 2, 2]
    [0, 1, 2, 3]
    

    The columns go with the prefixes "", "a", "ac" and "ace". The bottom-right entry, 3, is the answer.

    Python details worth knowing:

    • Build the rows with a comprehension. [[0] * (m + 1)] * (n + 1) repeats one row object, so changing one row changes them all. With n = 5 and m = 3, setting dp[1][1] = 7 on that table changes the second entry of every row. The comprehension creates a separate list for each row.
    • Negative indexes don't raise errors. dp[-1] is the last row. The loops start at 1, so i - 1 and j - 1 are never negative, but a loop starting at 0 would silently read the wrong cells.
    • Strings index by character. text1[i - 1] is a one-character string, and == compares contents.

    Complexity

    Time: O(n · m): the table has (n + 1) × (m + 1) entries, and each takes constant work. Space: O(n · m) for the table. Each row reads only itself and the row above, so two rows of m + 1 numbers would bring the space down to O(m). The lesson keeps the whole table, which is easier to follow.

    Edge cases and common mistakes

    • No common character. "abc" and "def" give 0.
    • Identical strings. "abc" and "abc" give 3.
    • Repeated letters. "aaa" and "aa" give 2.
    • Order matters. "ace" and "aec" give 2, not 3, since the characters must keep their order. "abc" and "cba" give 1.
    • Off-by-one indexing. Using text1[i] instead of text1[i - 1] raises an IndexError on the last row or column, or compares the wrong characters.
    • Subsequence versus substring. A substring must be contiguous; a subsequence may skip characters.

    Testing

    • "abcde", "ace" gives 3.
    • "abcbdab", "bdcaba" gives 4.
    • "abc", "def" gives 0.
    • "abc", "abc" gives 3.
    • "aaa", "aa" gives 2.
    • "abc", "cba" gives 1.
    Keep going with Python650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free