Minimum covering window: track unmet demand

Make validity a cheap question

A baseline enumerates each start and extends a count map until all requirements are covered. Repeating that scan costs O(n²) updates plus validity checks. A set is insufficient: required AAC needs two As. The reusable method is to name the expensive question, then maintain its answer incrementally. Let need[c] be required count minus current-window count, and missing be the number of required occurrences still absent. Negative need means harmless surplus.

When adding a required character, decrement missing only if its prior need was positive, then decrement need. When removing one, increment need first; if it becomes positive, increment missing. This update order distinguishes a required copy from surplus. Non-required characters need no map entries.

While missing is zero, record the candidate and advance left. This visits the shortest valid window ending at each right edge. A start discarded during shrinking cannot improve at a later right edge: its window would only get longer. Both boundaries move forward at most n times, giving expected O(n + m) time and O(k) auxiliary space for k required code points. The returned indices use O(1) space. Strictly shorter updates preserve the earliest tie. This proof depends on coverage being preserved by expansion; arbitrary window predicates do not automatically support two pointers.

Follow-up 1: matches must appear in required order

Predict what breaks when required="AC" means a subsequence in that order. Inventory sees CA as valid although the sequence is impossible.

Use state for progress through the required sequence, such as the latest viable start for each matched prefix. Update matching states backward per text character so one occurrence cannot advance several repeated required positions. An O(nm) dynamic program is a defensible baseline; the count invariant is gone.

Follow-up 2: several requirement sets share one text

Independent demand states remain correct but cost O(qn + total demand size). Do not claim one universal left boundary: different queries become valid at different positions. A senior candidate derives the exact update order and tests multiplicity and ties. A lead candidate sets query-count and retained-text budgets and measures whether shared preprocessing is justified by the workload.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/05-minimum-covering-window
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

def minimum_covering_window(text, required):
    if not isinstance(text, str) or not isinstance(required, str):
        raise ValueError("arguments must be strings")
    if not required:
        return 0, 0
    need = {}
    for char in required:
        need[char] = need.get(char, 0) + 1
    missing = len(required)
    left = 0
    best = None
    for right, char in enumerate(text):
        if char in need:
            if need[char] > 0:
                missing -= 1
            need[char] -= 1
        while missing == 0:
            if best is None or right + 1 - left < best[1] - best[0]:
                best = left, right + 1
            departing = text[left]
            if departing in need:
                need[departing] += 1
                if need[departing] > 0:
                    missing += 1
            left += 1
    return best

import itertools
import unittest
from collections import Counter
from solution import minimum_covering_window

class CoverTests(unittest.TestCase):
    def test_examples_and_ties(self):
        self.assertEqual(minimum_covering_window("ABAAC", "AAC"), (2, 5))
        self.assertEqual(minimum_covering_window("abxba", "ab"), (0, 2))
        self.assertIsNone(minimum_covering_window("ab", "aa"))
        self.assertEqual(minimum_covering_window("", ""), (0, 0))
        self.assertEqual(minimum_covering_window("🙂x🙂é", "🙂é"), (2, 4))
        with self.assertRaises(ValueError):
            minimum_covering_window("abc", None)

    def test_all_substrings_oracle(self):
        for n in range(6):
            for chars in itertools.product("ab", repeat=n):
                text = "".join(chars)
                for required in ["", "a", "b", "aa", "ab", "aab"]:
                    candidates = [(i, j) for i in range(n + 1) for j in range(i, n + 1)
                                  if not (Counter(required) - Counter(text[i:j]))]
                    expected = min(candidates, key=lambda pair: (pair[1] - pair[0], pair[0])) if candidates else None
                    self.assertEqual(minimum_covering_window(text, required), expected)

if __name__ == "__main__":
    unittest.main()