Minimum Window Substring

1. The obvious way

   Check every substring for coverage: O(n² x m).

2. The key insight

   Keep a tally of what the list still needs (it can go negative for surplus items) and a count of items still missing. Move the right edge: a needed item lowers the missing count. When nothing is missing the window is valid; move the left edge in as far as it stays valid (items with spares may leave) and record the shortest window. Then drop one needed item and keep looking. Every character enters and leaves at most once.

3. The algorithm
   1. Tally the needs from t; missing = len(t).
   2. Walk the right edge: if the character is still needed, missing goes down by 1. Lower its tally by 1.
   3. Nothing missing? Slide the left edge in while the character leaving has a spare (tally below 0).
   4. Record the window if it is the shortest. Then drop one needed character and keep walking.

Watch it run

best "ADOBEC"

from collections import Counter

def min_window(s, t):
    needs = Counter(t)                         # what the list still needs
    missing = len(t)
    left = 0
    best_start, best_end = 0, float("inf")
    for right, character in enumerate(s):
        if needs[character] > 0:
            missing -= 1                       # a needed item collected
        needs[character] -= 1
        if missing == 0:                       # everything collected: shrink
            while needs[s[left]] < 0:          # spare items can leave
                needs[s[left]] += 1
                left += 1
            if right - left < best_end - best_start:
                best_start, best_end = left, right
            needs[s[left]] += 1                # drop a needed item, search again
            missing += 1
            left += 1
    return "" if best_end == float("inf") else s[best_start : best_end + 1]

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.