How do you approach Longest Common Subsequence?

Use a 2-D table dp[i][j] for prefixes of length i and j.

What are common mistakes on Longest Common Subsequence?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Longest Common Subsequence

MediumAlgorithms

Description

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence keeps relative order but need not be contiguous. If there is none, return 0.

Example 1

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

Output: 3

Explanation: "ace" is the LCS.

Example 2

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

Output: 0

Explanation: No common subsequence.

Constraints

- 1 <= text1.length, text2.length <= 1000 - The strings consist of lowercase English letters

Longest Common Subsequence: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 7 test cases (5 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 2-step hint ladder

Use a 2-D table dp[i][j] for prefixes of length i and j.
On a character match, extend the diagonal; otherwise take the better of dropping one character.

The optimal approach

Show the approach: The approach

Classic 2-D DP. `dp[i][j]` is the LCS of `text1[:i]` and `text2[:j]`. If the last characters match, `dp[i][j] = dp[i-1][j-1] + 1`; otherwise `max(dp[i-1][j], dp[i][j-1])`.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.