Minimum Window Substring

Find the shortest substring that contains all required characters and counts.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Minimum Window Substring: Maintain the exact deficit count while the right boundary gains characters and the left boundary removes only proven surplus.

Input and goalFind the shortest substring that contains all required characters and counts.

Initialize required countsFor text "ABAAC" and required "AAC", L = 0, the next R is 0, need has A:2 and C:1, and missing = 3.

LRA0B1A2A3C4

rangeempty before reading index 0requiredneed A:2, C:1missing3bestnone

saved stateA2C1

Recognize it

Use it when a contiguous result must cover a multiset of required values and validity can be updated by adding or removing one boundary value.

Keep true

need[x] is the remaining deficit for x (negative means surplus), missing is the total number of required copies absent from [L..R], and best is the shortest valid window seen before the current transition.

Reuse it

When validity is monotone under expansion, grow until feasible, then remove leftmost surplus while feasible; a deficit counter can collapse a full multiset comparison into constant-time boundary updates.

Pattern: Grow, then shrink a sliding window.

Simple idea: Move the right side until every required character is present. Then move the left side while the window remains valid. Save the shortest valid window.

from collections import Counter

def min_window(text: str, required: str) -> str:
   if not required:
      return ""

   need = Counter(required)
   missing = len(required)
   left = 0
   best_start = 0
   best_length = len(text) + 1

   for right, char in enumerate(text):
      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

         left_char = text[left]
         need[left_char] += 1
         if need[left_char] > 0:
            missing += 1
         left += 1

   if best_length > len(text):
      return ""
   return text[best_start : best_start + best_length]

Cost: $O(n)$ time and $O(k)$ space.