798. Longest Shared Subsequence
Two radio stations each log the jingles they play during a day as a string of lowercase letters, one letter per jingle. A station manager wants to know how much of the daily running order the two logs have in common.
Given strings a and b, return the length of the longest string that can be obtained from both of them by deleting some characters (possibly none) while keeping the remaining characters in their original order. If the two logs have no letter in common, return 0.
Aim for O(n*m) time, where n and m are the lengths of the strings, and O(min(n, m)) extra space.
Example 1
- Input:
- a = "harvestmoon", b = "harmonyfest"
- Output:
- 6
- Explanation:
The longest shared subsequence is "harmon", which has length 6.
Example 2
- Input:
- a = "quillfeather", b = "pluckedquail"
- Output:
- 4
- Explanation:
The longest shared subsequence is "quil", which has length 4.
Example 3
- Input:
- a = "zxzxzx", b = "xzzxxz"
- Output:
- 4
- Explanation:
The longest shared subsequence is "xzzx", which has length 4.
Constraints
1 ≤ a.length, b.length ≤ 1000
a and b contain only lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n*m)
- Space
- O(min(n,m))