Longest sequence of events two traces share

HardAbout 40 minProblem 2 of 2 in Dynamic programmingDraft

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

  1. sharedSequence(["recv", "auth", "db", "cache", "send"], ["recv", "db", "retry", "db", "send"])returns 3recv, db, send.
  2. sharedSequence(["a", "b", "c"], ["x", "y"])returns 0
  3. sharedSequence(["a", "b", "c", "d"], ["b", "d", "a", "c"])returns 2

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.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open