LeetCode 1143 ·
Medium
Longest Common Subsequence
Find the length of the longest subsequence present in both strings.
Try it
Step through the core mechanic. The simulator below runs the advanced dp shape this problem is built on.
Interactive · LCS — "ACBDE" vs "ABCDE" match: 1+dp[i−1][j−1]; else max(dp[i−1][j], dp[i][j−1])
| ∅ | A | B | C | D | E | |
|---|---|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | · | · | · | · | · |
| C | 0 | · | · | · | · | · |
| B | 0 | · | · | · | · | · |
| D | 0 | · | · | · | · | · |
| E | 0 | · | · | · | · | · |
base row & column seeded
The approach
dp[i][j] over prefixes: if the characters match, 1 + dp[i−1][j−1]; else max(dp[i−1][j], dp[i][j−1]). The classic edit-distance-family grid.
| Aspect | Value |
|---|---|
| Pattern | Advanced DP |
| Recognise it by | Longest subsequence shared by two strings. |
| Time complexity | O(mn) |
| Space complexity | O(mn) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.