1143. Longest Common SubsequenceMedium

Longest Common Subsequence

MediumStringDynamic Programming·AmazonGoogleMicrosoft

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence is a string derived from another string by deleting some (or no) characters without changing the relative order of the remaining characters.

A common subsequence is a subsequence that appears in both strings.

Example 1:

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

Output:3

The longest common subsequence is "ace" with length 3.

Example 2:

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

Output:3

The longest common subsequence is "abc" with length 3.

Example 3:

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

Output:0

There is no common subsequence, so the result is 0.

Constraints:

1 ≤ text1.length, text2.length ≤ 1000
text1 and text2 consist of only lowercase English characters.

Naive Approach — Recursion + Memoization

Top-Down DP

🔄

Recursive Choices at Each Position

Time O(n·m)Space O(n·m)

At each pair of indices (i, j) in the two strings, there are two choices:

1If text1[i] == text2[j], this character is part of the LCS — take it and recurse on (i+1, j+1).
2Otherwise, try skipping one character from either string: max(lcs(i+1, j), lcs(i, j+1)).
3Cache the result in a memo table to avoid redundant subproblems.

Why convert to bottom-up: Recursion has call-stack overhead and cache misses. Bottom-up DP fills the table row by row — no recursion, same O(n·m) time and space.

def longestCommonSubsequence(text1, text2):
    memo = {}
    def dfs(i, j):
        if i == len(text1) or j == len(text2):
            return 0
        if (i, j) in memo: return memo[(i, j)]
        if text1[i] == text2[j]:
            memo[(i, j)] = 1 + dfs(i+1, j+1)
        else:
            memo[(i, j)] = max(dfs(i+1, j), dfs(i, j+1))
        return memo[(i, j)]
    return dfs(0, 0)

Optimal Approach — Bottom-Up 2D DP

O(n·m) Time

🗂️

Fill the DP Table Row by Row

Time O(n·m)Space O(n·m)

Build a 2D table where dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]. Row and column 0 are base cases (empty string), always 0.

1Match — text1[i-1] == text2[j-1]: extend the diagonal. dp[i][j] = 1 + dp[i-1][j-1].
2No match: carry the best result from either skipping a char in text1 or text2. dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
3Answer is at dp[n][m].

LCS DP Table

Current cell

Diagonal (match)

Up / Left (no match)

READYPress ▶ or step forward to begin.

—

Text 1

Text 2

Executing Code

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] = 1 + dp[i-1][j-1]

                else:

                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        return dp[n][m]

Discussion

…

Loading comments…

LeetMotion

Longest Common Subsequence

MediumStringDynamic Programming·AmazonGoogleMicrosoft

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence is a string derived from another string by deleting some (or no) characters without changing the relative order of the remaining characters.

A common subsequence is a subsequence that appears in both strings.

Example 1:

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

Output:3

The longest common subsequence is "ace" with length 3.

Example 2:

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

Output:3

The longest common subsequence is "abc" with length 3.

Example 3:

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

Output:0

There is no common subsequence, so the result is 0.

Constraints:

1 ≤ text1.length, text2.length ≤ 1000
text1 and text2 consist of only lowercase English characters.

Naive Approach — Recursion + Memoization

Top-Down DP

🔄

Recursive Choices at Each Position

Time O(n·m)Space O(n·m)

At each pair of indices (i, j) in the two strings, there are two choices:

1If text1[i] == text2[j], this character is part of the LCS — take it and recurse on (i+1, j+1).
2Otherwise, try skipping one character from either string: max(lcs(i+1, j), lcs(i, j+1)).
3Cache the result in a memo table to avoid redundant subproblems.

Why convert to bottom-up: Recursion has call-stack overhead and cache misses. Bottom-up DP fills the table row by row — no recursion, same O(n·m) time and space.

def longestCommonSubsequence(text1, text2):
    memo = {}
    def dfs(i, j):
        if i == len(text1) or j == len(text2):
            return 0
        if (i, j) in memo: return memo[(i, j)]
        if text1[i] == text2[j]:
            memo[(i, j)] = 1 + dfs(i+1, j+1)
        else:
            memo[(i, j)] = max(dfs(i+1, j), dfs(i, j+1))
        return memo[(i, j)]
    return dfs(0, 0)

Optimal Approach — Bottom-Up 2D DP

O(n·m) Time

🗂️

Fill the DP Table Row by Row

Time O(n·m)Space O(n·m)

Build a 2D table where dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]. Row and column 0 are base cases (empty string), always 0.

1Match — text1[i-1] == text2[j-1]: extend the diagonal. dp[i][j] = 1 + dp[i-1][j-1].
2No match: carry the best result from either skipping a char in text1 or text2. dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
3Answer is at dp[n][m].

LCS DP Table

Current cell

Diagonal (match)

Up / Left (no match)

READYPress ▶ or step forward to begin.

—

Text 1

Text 2

Executing Code

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] = 1 + dp[i-1][j-1]

                else:

                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        return dp[n][m]