Minimum Window Substring — Sliding Window

What does it solve?

Given strings S and T, find the shortest contiguous substring of S that contains every character of T, counting duplicates. If no such window exists, return the empty string.

Key insight: grow a window by moving right until it becomes valid (covers all of T), then shrink from left while it stays valid, recording the smallest. Each character enters and leaves the window at most once, so the whole scan is O(N).

The core idea

// grow right, then shrink left
need = freq(T); required = |need|
formed = 0, left = 0, best = ∞
for right in 0..n-1:
  window[S[right]]++
  if window[c] == need[c]: formed++
  while formed == required:
    best = min(best, right-left+1)
    window[S[left]]--; left++

Complexity

Time complexity

O(N + M)

N = |S|, M = |T|. Building the need map is O(M). Each of the two pointers advances at most N times, so the window scan is O(N).

Space complexity

O(K)

Two frequency maps over the distinct characters of T. K = number of unique characters, bounded by the alphabet size.

Examples & edge cases

Live animation — sliding window (grow right, shrink left)

inside window right pointer (char added) target char (in T) window valid → recorded best window so far

String S — window [left … right] —

Target coverage — need vs window

left = — right = — matched = — best = —

Step — of —

left pointer

—

window start

right pointer

—

window end

matched

—

unique chars met

Best length

—

not found yet

Select an example and press Play to start.

✓ Answer: —

Speed Medium

Step-by-step table

Step	Phase	left	right	char	window	Matched	Action	Best

C++ implementation

min_window_substring.cpp

#include <bits/stdc++.h>
using namespace std;

// Smallest substring of s that contains every char of t (with multiplicity)
string minWindow(string s, string t) {
    if (s.empty() || t.empty()) return "";

    unordered_map<char,int> need;
    for (char c : t) need[c]++;
    int required = need.size();      // distinct chars still to satisfy

    unordered_map<char,int> window;
    int formed = 0;                  // distinct chars currently satisfied
    int left = 0;
    int bestLen = INT_MAX, bestStart = 0;

    for (int right = 0; right < (int)s.size(); right++) {
        char c = s[right];
        window[c]++;
        if (need.count(c) && window[c] == need[c]) formed++;

        // shrink from the left while the window stays valid
        while (formed == required) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            char lc = s[left];
            window[lc]--;
            if (need.count(lc) && window[lc] < need[lc]) formed--;
            left++;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
}

int main() {
    cout << minWindow("ADOBECODEBANC", "ABC") << "\n"; // BANC
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars