ALG-H005HardSliding Window

Smallest Covering Substring

Find the shortest contiguous substring of text containing every character of required with at least the same multiplicity. Return the earliest window among ties, or an empty string if none exists. Empty required yields an empty string.

Contract

input text: string

input required: string

return string

Constraints

• 0 <= text length <= 10000

Examples

Example 1

text = "ADOBECODEBANC"

required = "ABC"

→ "BANC"

Example 2

text = "a"

required = "aa"

→ ""

5 judge tests (2 shown above). Target complexity: O(n+|required|).