Minimum Window Substring

An interactive, step-by-step visualisation of Minimum Window Substring.

Category: Sliding Window
Time complexity: O(n + m)
Space complexity: O(Σ)

Pseudocode

expand right, tracking how many required chars are satisfied
once all satisfied: try shrinking left, record best window
stop shrinking when a required char becomes unsatisfied

Reference implementation

need = Counter(t); missing = len(t)
lo = 0; best = None
for hi, ch in enumerate(s):
    if need[ch] &gt; 0: missing -= 1
    need[ch] -= 1
    while missing == 0:
        best = min(best, s[lo:hi+1], key=len)
        need[s[lo]] += 1
        if need[s[lo]] &gt; 0: missing += 1
        lo += 1

Open the interactive Minimum Window Substring visualisation →