Longest Shared Subsequence
Problem
Two versions of a document are reduced to strings first and second. A subsequence is what remains after deleting zero or more characters without reordering the rest (for example "ace" is a subsequence of "abcde").
Return the length of the longest string that is a subsequence of both first and second. Return 0 if they share no character.
Example 1
- Input:
- first = "planet", second = "plaque"
- Output:
- 4
"plae" can be read in order inside both strings.
Example 2
- Input:
- first = "kayak", second = "yak"
- Output:
- 3
"yak" itself appears in order inside "kayak" (positions 2, 3, 4).
Example 3
- Input:
- first = "abc", second = "xyz"
- Output:
- 0
Constraints
- 0 ≤ first.length, second.length ≤ 1000
- Both strings contain lowercase English letters only.
Hint
Show the first hint
Compare the strings prefix by prefix: what is the answer for first[:i] and second[:j]?
Walkthrough
How to approach it
01Clarify before coding
- Subsequence or substring? Subsequence: the characters need not be adjacent, only in order.
- Return the length or the string? Just the length.
- Can either string be empty? Yes, then the answer is 0.
02Brute force
Generate every subsequence of the shorter string and check, longest first, whether it is a subsequence of the other.
Cost: O(2^m · n): with 1000 characters, 2^1000 candidates.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.