Longest Common Subsequence

MEDIUM

Description

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

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

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

Approaches

Checkout 4 different approaches to solve Longest Common Subsequence. Click on different approaches to view the approach and algorithm in detail.

Recursion with Memoization (Top-Down DP)

This approach optimizes the brute-force recursion by using a memoization table (usually a 2D array) to store the results of already computed subproblems. By caching results, we avoid redundant calculations for the same pair of indices (i, j). This technique is a form of top-down dynamic programming.

Algorithm

Use the same recursive structure as the brute-force approach.
Create a 2D array memo[m][n] to store the results of subproblems, initialized with a value like -1.
In the recursive function solve(i, j), first check if memo[i][j] is already computed (i.e., not -1). If so, return the stored value.
If not computed, calculate the result using the same recursive logic.
Before returning the result, store it in memo[i][j] for future use.

The recursive structure is the same as the brute-force approach, but we enhance it with a cache to store intermediate results.

We introduce a 2D array, memo, of size m x n (where m is text1.length() and n is text2.length()) to store the results of solve(i, j).
We initialize the memo table with a special value (e.g., -1) to indicate that a subproblem has not been solved yet.
Inside the recursive function solve(i, j), before any computation, we first check if memo[i][j] has already been computed. If it has, we return the stored value immediately, avoiding a costly re-computation.
If the result is not in the memo table, we compute it using the same recursive logic as before.
After computing the result, we store it in memo[i][j] before returning it.

By storing results, we ensure that each subproblem (i, j) is solved only once.

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] memo = new int[m][n];
        for (int[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }
        return solve(text1, text2, 0, 0, memo);
    }

    private int solve(String text1, String text2, int i, int j, int[][] memo) {
        if (i == text1.length() || j == text2.length()) {
            return 0;
        }

        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        int result;
        if (text1.charAt(i) == text2.charAt(j)) {
            result = 1 + solve(text1, text2, i + 1, j + 1, memo);
        } else {
            int option1 = solve(text1, text2, i + 1, j, memo);
            int option2 = solve(text1, text2, i, j + 1, memo);
            result = Math.max(option1, option2);
        }
        
        memo[i][j] = result;
        return result;
    }
}

Complexity Analysis

Time Complexity: O(m * n). Each state `(i, j)` is computed only once. There are `m * n` possible states.Space Complexity: O(m * n) for the memoization table, plus O(m+n) for the recursion stack. The dominant factor is the memoization table.

Pros and Cons

Pros:

Drastically more efficient than brute-force, with polynomial time complexity.
Retains the intuitive top-down recursive structure, making it easy to reason about.

Cons:

Requires O(m*n) space for the memoization table, which can be significant.
For very deep recursion paths (not an issue with problem constraints), it could theoretically cause a stack overflow.

Code Solutions

Checking out 5 solutions in different languages for Longest Common Subsequence. Click on different languages to view the code.

public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        int m = text1.Length, n = text2.Length;
        int[, ] f = new int[m + 1, n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (text1[i - 1] == text2[j - 1]) {
                    f[i, j] = f[i - 1, j - 1] + 1;
                } else {
                    f[i, j] = Math.Max(f[i - 1, j], f[i, j - 1]);
                }
            }
        }
        return f[m, n];
    }
}

Video Solution

Watch the video walkthrough for Longest Common Subsequence

Patterns:

Dynamic Programming

Data Structures:

String

Companies:

Accolite |ByteDance |DoorDash |Nutanix |