LeetCode 76 Minimum Window Substring - Example and Complexity Analysis

Trace s = "ADOBEC" with t = "ABC".

Initialize: need = {A: 1, B: 1, C: 1}, have = 0, left = 0.

right = 0: 'A' needed. need[A] = 0. have = 1.

right = 1: 'D' not in need. Skip.

right = 2: 'O' not in need. Skip.

right = 3: 'B' needed. need[B] = 0. have = 2.

right = 4: 'E' not in need. Skip.

right = 5: 'C' needed. need[C] = 0. have = 3. Now have == len(need).

Valid window: "ADOBEC". Record it.

Contract: remove 'A' at left = 0. need[A] = 1. have = 2. Window invalid.

Move left = 1. Stop contracting (window invalid).

Return "ADOBEC".

Each character enters and leaves at most once. $O(n + m)$ time. Frequency maps use $O(k)$ space for $k$ distinct characters.