Skip to the code
cf.
+50 XP

#147 Smallest Snippet With Every Keyword Letter

hard

A search results page shows a short snippet of each document doc around the query query. The snippet must be a slice of neighboring characters of doc that contains every character of query, including repeats: if query has two as, the snippet needs at least two as.

Write smallestSnippet(doc, query) that returns the shortest such slice. If several slices have the shortest length, return the one that starts first. If no slice works, return "".

Example 1

Input: doc = "RAZBXCYACBZ", query = "ABC"
Output: "ACB"

ACB has A, B, and C and is the shortest such slice.

Example 2

Input: doc = "a", query = "aa"
Output: ""

doc has only one a.

Constraints

  • 1 <= doc.length, query.length <= 100000
  • Both strings contain upper and lower case letters; case matters.
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).