Free Strings lessonsStrings · Stage 3 · Windows on text · Step 4

Cover everything, then tighten

The shortest stretch of text that contains every character of a pattern. About 14 minutes.

A shopping list for the window

You need to buy an A, a B and a C, and the shops are in a row along the street. What's the shortest stretch of street that has everything on your list?

Keep a shopping list: how many of each letter you still need, and how many items are missing in total. Grow the window on the right. Each letter that enters ticks off one item, but only if you still needed it.

Nothing missing: the window covers the whole list.

s = "ADOBECODEBANC", t = "ABC"

leftright

best: "ADOBEC"
missing: 0

Grow until nothing is missing: "ADOBEC" has an A, a B and a C. Record it: length 6.

Move 1 of 6

Tighten while it still covers

Once nothing is missing, note the window, then try dropping letters from the left. Dropping an extra copy costs nothing. Dropping one you needed puts it back on the list, and the window has to grow again.

Grow until covered, tighten until not, repeat. For "ADOBECODEBANC" and "ABC", the shortest covering stretch is "BANC".

Covered? note it, then drop from the left.

Dropped a needed letter: grow again.

In code

need = {}
for ch in t:
    need[ch] = need.get(ch, 0) + 1
missing = len(t)
left, start, size = 0, 0, float("inf")
for right, ch in enumerate(s):
    if need.get(ch, 0) > 0:
        missing -= 1
    need[ch] = need.get(ch, 0) - 1
    while missing == 0:
        width = right - left + 1
        if width < size:
            start, size = left, width
        need[s[left]] += 1
        if need[s[left]] > 0:
            missing += 1
        left += 1
if size == float("inf"):
    return ""
return s[start:start + size]

Quick check

You need an A and a B. The window "ADOBEC" covers both. Can it drop its first letter?

ANo: that A is needed
BYes: it's a spare
COnly if the B goes too

Show the answer

No: that A is needed. It's the only A in the window, so dropping it puts A back on the list.

Your problem

Smallest covering window

You get a text s and a pattern t. Return the shortest run of consecutive characters of s that contains every character of t, with repeats (if t has two a's, the window needs two). If several are equally short, return the leftmost. If there is none, return "".

Example

s = "ADOBECODEBANC", t = "ABC" → "BANC"

0 ≤ length of s ≤ 100,000 · 1 ≤ length of t ≤ 100,000 · letters only

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.