MediumStringDynamic Programming

Longest Common Subsequence

1 approach, code in every language

You are given two strings, text1 and text2. A subsequence keeps the original relative order of characters but may skip any number of them; a common subsequence is one that appears in both strings.

Return the length of the longest subsequence present in both text1 and text2. If no common subsequence exists, return 0.

Example 1

Input: text1 = "abcde", text2 = "ace"

Output: 3

The subsequence "ace" appears in both strings and no longer common subsequence exists, so the answer is 3.

Example 2

Input: text1 = "abc", text2 = "def"

Output: 0

The two strings share no characters, so the longest common subsequence has length 0.

Constraints

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of lowercase English characters.

Prefix Grid Dynamic Programming

Fill a grid where each cell stores the longest common subsequence of two prefixes.

Loading animation…

Intuition

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. If either prefix is empty the answer is 0, which is why the top row and left column stay zero and need no special handling. When the current characters text1[i-1] and text2[j-1] match, that shared character can extend the best subsequence of the smaller prefixes, giving dp[i][j] = dp[i-1][j-1] + 1. When they do not match, the best we can do is drop one of the two characters, so dp[i][j] is the larger of dp[i-1][j] and dp[i][j-1]. Processing rows and columns in increasing order means every value we read has already been finalized, and dp[m][n] holds the final answer.

Algorithm walkthrough

1Create a grid of size (m + 1) by (n + 1) initialized to zero, so the empty-prefix base cases are already handled.
2Loop i from 1 to m and j from 1 to n to consider each pair of prefixes.
3When text1[i-1] equals text2[j-1], set dp[i][j] to dp[i-1][j-1] + 1 to include the shared character.
4When the characters differ, take the maximum of dp[i-1][j] and dp[i][j-1] to drop one character.
5Continue until the entire grid is populated in order.
6Return dp[m][n], the length of the longest common subsequence of the full strings.

Implementation

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 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[m][n]

Time

O(m * n)

Space

O(m * n)

Each grid cell is filled once using three already-computed neighbors. Because every row depends only on the previous one, the space can be trimmed to O(n) with a rolling row if needed.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Shared Checkpoint Order is our own problem on the technique behind Longest Common Subsequence: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free