Longest sequence of events two traces share
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
Two traces of the same request, from a healthy and a failing run, list event names in order. To compare them, find the longest sequence of events that appears in both, in the same order, though not necessarily next to each other.
Return the length of that longest shared sequence.
- 0 ≤ a.length, b.length ≤ 3,000
Examples
sharedSequence(["recv", "auth", "db", "cache", "send"], ["recv", "db", "retry", "db", "send"])returns3recv, db, send.sharedSequence(["a", "b", "c"], ["x", "y"])returns0sharedSequence(["a", "b", "c", "d"], ["b", "d", "a", "c"])returns2
Hints
Hint 1 of 2
Let len[i][j] be the answer for the first i events of a and the first j of b. If a[i - 1] equals b[j - 1], what is len[i][j]? And if not?
Hint 2 of 2
If they match, it is len[i - 1][j - 1] + 1; otherwise the larger of len[i - 1][j] and len[i][j - 1]. You only need the previous row at any time.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Compare the last events of the two prefixes. If they match, the longest shared sequence of the prefixes ends with that event, and before it comes the longest shared sequence of both prefixes one shorter. If they do not match, one of the two events is not in the answer, so drop either and keep the better result.
That gives a table: len[i][j] for the first i events of a and the first j of b, each entry from its three neighbours above and to the left. Filling it row by row touches 9 million cells for two 3,000-event traces, which is quick; the same recursion without the table is exponential.
Each row only reads the row before it, so two arrays of length b.length + 1 are enough. The longest run of adjacent events is a different question, and gives 1 for the first example instead of 3.
function sharedSequence(a, b) {
let prev = new Array(b.length + 1).fill(0);
for (let i = 1; i <= a.length; i++) {
const row = new Array(b.length + 1).fill(0);
for (let j = 1; j <= b.length; j++)
row[j] = a[i - 1] === b[j - 1] ? prev[j - 1] + 1 : Math.max(prev[j], row[j - 1]);
prev = row;
}
return prev[b.length];
}Complexity. O(n × m) time, O(m) space with two rows.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.