Smallest Covering Shift

hard

A staffing system encodes each hour of the day as a character: schedule[i] is the skill on duty during hour i. An auditor needs one contiguous block of hours that covers every skill in the requirement string required — including duplicates (if required lists a skill twice, the block needs at least two hours of it).

Return the shortest such contiguous block of schedule. If no block covers the requirement, return the empty string "". The test inputs guarantee the shortest block is unique when it exists.

Example 1

in schedule = "ADOBECODEBANC", required = "ABC"

out "BANC"

The shortest block containing A, B and C.

Example 2

in schedule = "a", required = "a"

out "a"

Example 3

in schedule = "a", required = "aa"

out ""

Two a's required, only one available.

Constraints

· 1 <= len(schedule), len(required) <= 2000
· letters are ASCII uppercase and lowercase
· shortest covering block is unique if it exists