Scale Engineer

Longest Common Subsequence

Med
#1076Time: O(m * n). Each state `(i, j)` is computed only once. There are `m * n` possible states.Space: O(m * n) for the memoization table, plus O(m+n) for the recursion stack. The dominant factor is the memoization table.9 companies
Patterns
Dynamic Programming
Data structures
String
Companies
AccoliteByteDanceDoorDashNutanix

Prompt

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

4 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

O(m * n). Each state `(i, j)` is computed only once. There are `m * n` possible states.

Space

O(m * n) for the memoization table, plus O(m+n) for the recursion stack. The dominant factor is the memoization table.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem