049. Minimum Covering Substring

Interview · Download this solution · All solutions and shared helpers

Problem

Return the shortest substring of source containing every character occurrence required by target. Extra characters are allowed. Break equal-length ties by earliest start. Return an empty string when target is empty or no cover exists. Matching is case-sensitive.

Examples

Example 1

minimum_cover("ADOBECODEBANC", "ABC")
=> 'BANC'

Every required character is covered in four positions.

Example 2

minimum_cover("a", "aa")
=> ''

One occurrence cannot satisfy two required copies.

Example 3

minimum_cover("abc", "")
=> ''

The empty target has the designated empty cover.

Reveal the worked solution and reasoning

Why this mechanism works

Track outstanding demand rather than merely distinct matches. A negative remaining count represents surplus copies in the window. The total missing occurrence count reaches zero exactly when all demand is covered. Record a valid window before removing its left character, then see whether that removal creates new unmet demand.

State and boundaries

need stores required count minus current-window count. missing counts unfulfilled required occurrences; negative need entries indicate surplus.

Protocol

Count target demand and total missing.
Add each incoming character, reducing missing only if it was still needed.
While missing is zero, record a strict length improvement.
Release the left character.
Increase missing if its remaining demand becomes positive.

Visualization

target ABC: missing 3
ADOBEC -> missing 0, first cover
shrink/expand -> BANC, length 4

Python implementation

from collections import Counter

def minimum_cover(source, target):
    if not target:
        return ''
    need = Counter(target)
    missing = len(target)
    left = best_start = 0
    best_length = len(source) + 1
    for right, char in enumerate(source):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
        while missing == 0:
            length = right - left + 1
            if length < best_length:
                best_start, best_length = left, length
            old = source[left]
            need[old] += 1
            if need[old] > 0:
                missing += 1
            left += 1
    if best_length > len(source):
        return ''
    return source[best_start:best_start + best_length]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

minimum_cover("ADOBECODEBANC", "ABC")

L4 minimum_cover: if not target:
source='ADOBECODEBANC'; target='ABC'

L6 minimum_cover: need = Counter(target)
source='ADOBECODEBANC'; target='ABC'; need={'A':1, 'B':1, 'C':1}

L7 minimum_cover: missing = len(target)
source='ADOBECODEBANC'; target='ABC'; need={'A':1, 'B':1, 'C':1}; missing=3

L8 minimum_cover: left = best_start = 0
source='ADOBECODEBANC'; target='ABC'; need={'A':1, 'B':1, 'C':1}; missing=3; left=0; best_start=0

L9 minimum_cover: best_length = len(source) + 1
source='ADOBECODEBANC'; target='ABC'; need={'A':1, 'B':1, 'C':1}; missing=3; left=0; best_start=0; best_length=14

L10 minimum_cover: for right, char in enumerate(source):
source='ADOBECODEBANC'; target='ABC'; need={'A':1, 'B':1, 'C':1}; missing=3; left=0; best_start=0; best_length=14; right=0; char='A'

L12 minimum_cover: missing -= 1
source='ADOBECODEBANC'; target='ABC'; need={'A':1, 'B':1, 'C':1}; missing=2; left=0; best_start=0; best_length=14; right=0; char='A'

L13 minimum_cover: need[char] -= 1
source='ADOBECODEBANC'; target='ABC'; need={'A':0, 'B':1, 'C':1}; missing=2; left=0; best_start=0; best_length=14; right=0; char='A'

... 66 intermediate state changes omitted ...

L18 minimum_cover: old = source[left]
source='ADOBECODEBANC'; target='ABC'; need={'A':0, 'B':0, 'C':0, 'D':0, 'O':0, ...}; missing=0; left=9; best_start=9; best_length=4; right=12; char='C'; length=4; old='B'

L19 minimum_cover: need[old] += 1
source='ADOBECODEBANC'; target='ABC'; need={'A':0, 'B':1, 'C':0, 'D':0, 'O':0, ...}; missing=0; left=9; best_start=9; best_length=4; right=12; char='C'; length=4; old='B'

L21 minimum_cover: missing += 1
source='ADOBECODEBANC'; target='ABC'; need={'A':0, 'B':1, 'C':0, 'D':0, 'O':0, ...}; missing=1; left=9; best_start=9; best_length=4; right=12; char='C'; length=4; old='B'

L22 minimum_cover: left += 1
source='ADOBECODEBANC'; target='ABC'; need={'A':0, 'B':1, 'C':0, 'D':0, 'O':0, ...}; missing=1; left=10; best_start=9; best_length=4; right=12; char='C'; length=4; old='B'

Result: 'BANC'. Every required character is covered in four positions.

minimum_cover("a", "aa")

L4 minimum_cover: if not target:
source='a'; target='aa'

L6 minimum_cover: need = Counter(target)
source='a'; target='aa'; need={'a':2}

L7 minimum_cover: missing = len(target)
source='a'; target='aa'; need={'a':2}; missing=2

L8 minimum_cover: left = best_start = 0
source='a'; target='aa'; need={'a':2}; missing=2; left=0; best_start=0

L9 minimum_cover: best_length = len(source) + 1
source='a'; target='aa'; need={'a':2}; missing=2; left=0; best_start=0; best_length=2

L10 minimum_cover: for right, char in enumerate(source):
source='a'; target='aa'; need={'a':2}; missing=2; left=0; best_start=0; best_length=2; right=0; char='a'

L12 minimum_cover: missing -= 1
source='a'; target='aa'; need={'a':2}; missing=1; left=0; best_start=0; best_length=2; right=0; char='a'

L13 minimum_cover: need[char] -= 1
source='a'; target='aa'; need={'a':1}; missing=1; left=0; best_start=0; best_length=2; right=0; char='a'

Result: ''. One occurrence cannot satisfy two required copies.

Why the solution is correct

Ingestion fulfills one missing occurrence exactly when prior demand is positive. Releasing a character breaks coverage exactly when updated demand becomes positive. The shrink loop therefore records valid candidates through the last satisfying boundary; strict replacement preserves the earliest equal-length answer.

Time and space

O(n+m) expected time and O(u) frequency space, plus the returned substring; u includes encountered source characters in this implementation.

Common mistakes

Counting only distinct characters misses repeated demand such as AABC. Testing validity after releasing a required character can save an invalid cover.

Reasoning card

State: need stores required count minus current-window count. missing counts unfulfilled required occurrences; negative need entries indicate surplus.

Invariant: formed accurately counts satisfied character requirements.

Decision to rehearse: Expand until all requirements are met; shrink while still valid.

Finish: Increase missing if its remaining demand becomes positive

Transfer exercise

Return all shortest covers rather than the earliest one, carefully separating strict improvements from ties.