Coding interview problems ā€ŗ Sliding Window

šŸŖŸ Sliding Window Hard

Minimum Window Substring

Minimum Window Substring explained: expand the window until it covers every needed character, then shrink it from the left. O(n) sliding window, tested Python.

Also searched as: smallest window containing all characters Ā· minimum window substring sliding window

šŸŖŸ

Try it live Free

Sliding Window

Watch the window add the element entering and drop the one leaving. In this problem the window stretches until it covers t, then contracts from the left, and the smallest valid stretch is the answer.

Also useful: Hash Tables

Open the playground ā†’

The problem

Given strings s and t, return the shortest substring of s that contains every character of t, counting duplicates. Return an empty string if no such window exists.

Inputs = "ADOBECODEBANC", t = "ABC"
Output"BANC"
Inputs = "a", t = "aa"
Output""

s has only one a.

The key insight

Expand the right edge until the window covers t, then shrink the left edge as far as it can go while still covering it, recording the smallest window. A counter of how many characters are still missing lets you know in O(1) whether the window covers t.

Brute force first: Checking every substring of s for coverage is O(nĀ² Ā· m) or worse.

Step-by-step approach

  1. Count the characters of t in need and set missing = len(t).
  2. Move right across s; if need[ch] > 0, decrement missing. Always decrement need[ch] (it can go negative for extras).
  3. While missing == 0: record the window if it is the smallest; then give back s[left] by incrementing need; if that count becomes positive, missing goes up by 1; move left.
  4. Return the smallest recorded window, or an empty string.

Python solution

PYTHON 3tested
from collections import Counter


def min_window(s, t):
    if not t or not s:
        return ""
    need = Counter(t)
    missing = len(t)
    left = 0
    best = (float("inf"), 0, 0)            # (length, start, end)
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1                      # negative = extra copies
        while missing == 0:                # window covers t: shrink it
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right + 1)
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return "" if best[0] == float("inf") else s[best[1]:best[2]]

Complexity

TimeO(n + m)
SpaceO(k)

Each index of s enters and leaves the window once, and t is counted once. The counter holds at most k distinct characters.

Common mistakes

Frequently asked questions

What is the time and space complexity of Minimum Window Substring?

O(n + m) time where n = len(s) and m = len(t), since each index of s enters and leaves the window once. Space is O(k) for the character counts.

Why can need counts go negative?

A negative count means the window has more copies of that character than t needs. Those extras can be dropped from the left without breaking coverage.

What does the missing counter track?

How many characters of t, counting duplicates, are still not covered by the window. When it reaches 0 the window is valid.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

šŸ“‹ 2-minute readiness check The full placement path

All coding interview problems More Sliding Window Sliding Window lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.