Longest Common Subsequence
Medium · 2-D Dynamic Programming · String · Dynamic Programming
Problem
Return the length of the longest subsequence common to both text1 and text2.
A subsequence keeps the original order but may skip characters; it need not be contiguous.
Examples
Input: text1 = "abcde", text2 = "ace" Output: 3
"ace" appears in order in both.
Input: text1 = "abc", text2 = "abc" Output: 3
Input: text1 = "abc", text2 = "def" Output: 0
Nothing in common.
Constraints
- 1 <= len(text1), len(text2) <= 1000
- Lowercase English letters
Approaches
- Top-down with memoisation — time O(m · n), space O(m · n)
Related problems
Start free on Cariara · Coding problems · System design studio
