Shortest stretch of a trace that touches every service

HardAbout 40 minProblem 3 of 3 in Sliding windowDraft

The problem

A distributed trace lists, in order, the name of the service that wrote each log entry. required lists distinct service names you are investigating.

Return the length of the shortest contiguous stretch of entries that contains every name in required at least once.

Return 0 if required is empty, and -1 if no stretch contains them all.

  • 0 ≤ entries.length ≤ 200,000
  • 0 ≤ required.length ≤ 50
  • names in required are distinct

Examples

  1. shortestSpan(["api", "db", "api", "cache", "db"], ["db", "cache"])returns 2cache, db at the end.
  2. shortestSpan(["api", "api"], ["db"])returns -1db never appears.
  3. shortestSpan(["api"], [])returns 0Nothing to cover.

Hints

Hint 1 of 2

Grow the window to the right until it covers every required name. Then it is a candidate; can it lose anything from the left and still cover them?

Hint 2 of 2

Keep a map from name to how many times it is in the window, and a count of required names that are present at least once. Shrink from the left while that count equals required.length.

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