Longest Common Subsequence – Solution & Complexity

Q: What is the time and space complexity of Longest Common Subsequence?

The optimal Longest Common Subsequence solution runs in `O(m*n)` time and `O(m*n)` space. 2D DP over string prefixes: on a character match take the diagonal + 1, otherwise carry forward the best of top/left; rolling rows can reduce space when only the length is needed.

Q: What is the most efficient way to solve Longest Common Subsequence?

2D DP over string prefixes: on a character match take the diagonal + 1, otherwise carry forward the best of top/left; rolling rows can reduce space when only the length is needed. This gives `O(m*n)` time complexity, and is a classic strings and dynamic programming problem.

Q: How do you solve Longest Common Subsequence in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

We provide a worked Longest Common Subsequence solution in Python, JavaScript, Java, Go, Rust, C++ & Ruby with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Longest Common Subsequence an easy or hard interview question?

Longest Common Subsequence is generally rated **Medium**. It tests strings and dynamic programming, which are common coding-interview patterns.

Solution Walkthrough

Step 1: Understand subsequences and why brute force fails
- A subsequence preserves relative order, but it can skip characters, so "ace" is a subsequence of "abcde" while "aec" is not.
- A brute-force idea is to generate every subsequence of one string and check whether it appears in the other. That quickly explodes to 2^m or 2^n possibilities.
- We need a way to reuse overlapping work across prefixes of both strings, which leads naturally to dynamic programming.

Step 2: Start from the naive recursion

Let dfs(i, j) mean the LCS length using text1[i:] and text2[j:].
If the current characters match, they can contribute 1 plus the best answer for the remaining suffixes.
Otherwise, we must try skipping one character from either string and keep the better result. This is correct, but without caching it revisits the same (i, j) states many times.

def longest_common_subsequence(text1: str, text2: str) -> int:
    def dfs(i: int, j: int) -> int:
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + dfs(i + 1, j + 1)
        return max(dfs(i + 1, j), dfs(i, j + 1))

    return dfs(0, 0)

Step 3: Cache overlapping states with memoization
- The recursive version recomputes the same suffix pairs like (i, j) again and again.
- Memoization stores each solved state once, turning the exponential tree of calls into at most m * n distinct subproblems.
- This top-down approach already reaches optimal time, but an iterative bottom-up table is often simpler to reason about and easier to visualize in interviews.

Step 4: Build the bottom-up 2D DP table

Let dp[i][j] be the LCS length of the prefixes text1[:i] and text2[:j].
If text1[i - 1] == text2[j - 1], then those matching characters extend the best answer for the smaller prefixes: dp[i][j] = dp[i - 1][j - 1] + 1.
Otherwise, the best subsequence must skip one side's current character, so dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).
Filling the table row by row gives the final answer at dp[m][n].

def longest_common_subsequence(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]

Step 5: Dry run on `text1 = "abcde"`, `text2 = "ace"`
We build a (m + 1) x (n + 1) table where rows are prefixes of text1 and columns are prefixes of text2. The first row and first column stay 0 because an empty string has LCS length 0 with anything.

dp[i][j] "" a c e
"" 0 0 0 0
a 0 1 1 1
ab 0 1 1 1
abc 0 1 2 2
abcd 0 1 2 2
abcde 0 1 2 3

The last cell is 3, so the longest common subsequence length is 3.
Step 6: Common mistakes
- Mixing up subsequences and substrings: subsequences can skip characters, substrings must stay contiguous.
- Using text1[i] and text2[j] while filling dp[i][j] for prefixes. In the table, the current characters are text1[i - 1] and text2[j - 1].
- Forgetting the extra zero-padded row and column, which causes off-by-one errors in the recurrence.
- On a mismatch, taking dp[i - 1][j - 1] directly instead of max(dp[i - 1][j], dp[i][j - 1]).
Step 7: Edge cases to test mentally
- If either string is empty, the answer is 0.
- If the strings share no characters in order, the answer stays 0 across the table.
- If the strings are identical, the answer is the full string length.
- Repeated characters still need order-aware matching, so you cannot greedily pair the first equal letter you see without considering future matches.

`dp[i][j]`	a	c	e
""	0	0	0
a	1	1	1
ab	1	1	1
abc	1	2	2
abcd	1	2	2
abcde	1	2	3

Step 8: Final full solution and complexity

Use bottom-up DP over all prefix pairs. This solves m * n subproblems, each in O(1) time, so the total time is O(m*n). The full table uses O(m*n) space, and a rolling-row optimization can reduce that to O(min(m, n)) when you only need the length.

def longest_common_subsequence(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]

Longest Common Subsequence – Solution & Complexity

Solution Walkthrough

Step 1: Understand subsequences and why brute force fails

Step 2: Start from the naive recursion

Step 3: Cache overlapping states with memoization

Step 4: Build the bottom-up 2D DP table

Step 5: Dry run on `text1 = "abcde"`, `text2 = "ace"`

Step 6: Common mistakes

Step 7: Edge cases to test mentally

Step 8: Final full solution and complexity

FAQ

What is the time and space complexity of Longest Common Subsequence?

What is the most efficient way to solve Longest Common Subsequence?

How do you solve Longest Common Subsequence in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is Longest Common Subsequence an easy or hard interview question?

See also

Longest Common Subsequence – Solution & Complexity

Solution Walkthrough

1Step 1: Understand subsequences and why brute force fails

2Step 2: Start from the naive recursion

3Step 3: Cache overlapping states with memoization

4Step 4: Build the bottom-up 2D DP table

5Step 5: Dry run on `text1 = "abcde"`, `text2 = "ace"`

6Step 6: Common mistakes

7Step 7: Edge cases to test mentally

8Step 8: Final full solution and complexity

FAQ

What is the time and space complexity of Longest Common Subsequence?

What is the most efficient way to solve Longest Common Subsequence?

How do you solve Longest Common Subsequence in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is Longest Common Subsequence an easy or hard interview question?

See also

Step 1: Understand subsequences and why brute force fails

Step 2: Start from the naive recursion

Step 3: Cache overlapping states with memoization

Step 4: Build the bottom-up 2D DP table

Step 5: Dry run on `text1 = "abcde"`, `text2 = "ace"`

Step 6: Common mistakes

Step 7: Edge cases to test mentally

Step 8: Final full solution and complexity