Skip to content

Volume ITechnology

4.6.5 — Minimum Window Substring ​

LeetCode 76 · Hard · ★ Blind 75

The problem ​

You are given two strings, s and t. Return the shortest substring of s that contains every character of t, including repeats. If no such substring exists, return the empty string "".

s = "ADOBECODEBANC", t = "ABC"   →  "BANC"
s = "a",             t = "a"     →  "a"
s = "a",             t = "aa"    →  ""      (t needs two a's, s has only one)

Both strings can have up to 100,000 English letters, upper or lower case. The problem promises that if an answer exists, there is only one shortest one.

"Including repeats" is the detail that decides the solution. If t is "AABC", the window must contain two As, not just one. That is why we need counts, not just a set of letters.

What the problem is really asking ​

Picture walking along s with a basket. You want the shortest stretch of s whose letters, dropped into the basket, cover everything on the shopping list t, with enough copies of each.

So the question is: what is the shortest window of s that "covers" t? That is a sliding window, but it wants the shortest valid window, not the longest. That changes the shape of the loop.

The brute force, and where it wastes work ​

Try every substring of s, count its letters, and check whether it covers t.

python
from collections import Counter

def minWindow(s, t):
    need = Counter(t)
    best = ""
    for i in range(len(s)):
        for j in range(i, len(s)):
            window = Counter(s[i:j + 1])
            if all(window[c] >= need[c] for c in need):
                if best == "" or j - i + 1 < len(best):
                    best = s[i:j + 1]
                break               # longer windows from i cannot be shorter
    return best

This is about O(n^2) windows, and each one is recounted from scratch, so it is O(n^3) in the worst case.

The waste in one sentence: neighbouring windows differ by one letter, but every window is recounted, and every check scans the whole shopping list.

The idea ​

Recall the window rule from 4.6.2. For the longest window, you shrink while the window is broken, and record after repairing it. For the shortest window, it flips:

  1. Grow the right edge until the window becomes valid, meaning it covers t.
  2. Then shrink from the left for as long as it stays valid, recording the length each time.
  3. The moment it breaks, stop shrinking and go back to growing.

Think of a shopping trip on a conveyor belt. You need 2 apples, 1 banana and 1 carrot. You keep grabbing items until your basket finally holds everything. Then you look at the first item you grabbed. If it is a box of cereal, or a third apple you do not need, you put it back. You keep putting things back until one more would ruin the recipe. That trimmed basket is your best attempt so far. Then you start grabbing again, to see if a shorter stretch exists further along.

Checking "is the window valid?" in one step ​

The slow way to check validity is to compare every letter's count each time. There is a neat way to make it a single comparison. Keep one number:

  • required: how many different letters of t do not yet have enough copies in the window.

At the start, no letter is satisfied, so required is the number of different letters in t. For t = "ABC" that is 3. For t = "AABC" it is also 3, because there are three different letters.

  • When a letter's count in the window reaches exactly the count t needs, one more letter is satisfied, so required goes down by 1.
  • When a letter's count drops below what t needs, that letter is unsatisfied again, so required goes up by 1.

The window is valid exactly when required == 0.

The word "exactly" matters. Suppose t needs two As and the window already holds three. Adding a fourth A does not change whether the window is valid. So required must only move when a count crosses the needed amount, not every time it changes.

The solution ​

python
from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t or len(t) > len(s):                    # (1)
            return ""

        need = Counter(t)                                        # (2)
        required = len(need)                                     # (3)
        window = {}

        left = 0
        best_len = float('inf')                                  # (4)
        best_start = 0

        for right in range(len(s)):                              # (5)
            c = s[right]
            window[c] = window.get(c, 0) + 1
            if c in need and window[c] == need[c]:               # (6)
                required -= 1

            while required == 0:                                 # (7)
                if right - left + 1 < best_len:                  # (8)
                    best_len = right - left + 1
                    best_start = left

                lc = s[left]                                     # (9)
                window[lc] -= 1
                if lc in need and window[lc] < need[lc]:         # (10)
                    required += 1
                left += 1

        if best_len == float('inf'):                             # (11)
            return ""
        return s[best_start:best_start + best_len]
ts
function minWindow(s: string, t: string): string {
  if (!s || !t || t.length > s.length) return "";                // (1)

  const need = new Map<string, number>();                        // (2)
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
  let required = need.size;                                      // (3)
  const window = new Map<string, number>();

  let left = 0;
  let bestLen = Infinity;                                        // (4)
  let bestStart = 0;

  for (let right = 0; right < s.length; right++) {               // (5)
    const c = s[right];
    window.set(c, (window.get(c) ?? 0) + 1);
    if (need.has(c) && window.get(c) === need.get(c)) required--;  // (6)

    while (required === 0) {                                     // (7)
      if (right - left + 1 < bestLen) {                          // (8)
        bestLen = right - left + 1;
        bestStart = left;
      }
      const lc = s[left];                                        // (9)
      window.set(lc, window.get(lc)! - 1);
      if (need.has(lc) && window.get(lc)! < need.get(lc)!) required++;  // (10)
      left++;
    }
  }

  return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);  // (11)
}

Line by line ​

(1) Quick exits. If either string is empty, or t is longer than s, no window can cover t.

(2) The shopping list. Counter(t) maps each letter of t to how many copies are needed. For "AABC" it is {A: 2, B: 1, C: 1}.

(3) required. The number of different letters not yet satisfied. len(need) is the number of keys in the map, which is the number of different letters. Using len(t) here instead is the most common bug on this problem. For "AABC", len(t) is 4 but there are only 3 letters to satisfy, so required would never reach 0.

(4) The best window so far. We store its start position and length, not the substring itself. best_len starts at infinity so that the first valid window always beats it.

(5) Grow the window to the right, one letter per turn, and count the new letter.

(6) Did this letter just become satisfied? Only if its count now equals the needed count. We use ==, not >=. With >=, every extra copy beyond the need would lower required again, and it would go below zero.

(7) While the window is valid, try to shrink it. This loop only runs when the window covers t.

(8) Record before shrinking. Right now the window is valid. If it is shorter than the best so far, remember where it starts and how long it is.

(9) Drop the leftmost letter. Its count goes down by one.

(10) Did that break the window? If the dropped letter is on the list and its count is now below the need, that letter is unsatisfied again, so required goes up. That makes the while condition false, the shrinking stops, and the for loop goes back to growing. Here we use <, the mirror of the == in line (6). Only the moment a count drops below the need counts.

Then left moves forward.

(11) Build the answer once, at the end. If best_len is still infinity, no valid window was ever found. Otherwise slice the string once.

Why not save the substring each time in line (8)? Because cutting a substring copies its letters, which takes time proportional to its length. Doing that inside the loop could cost up to n steps each time, and the whole solution would quietly become O(n^2). Saving two numbers and slicing once keeps it linear.

Trace ​

Take s = "ADOBECODEBANC" and t = "ABC". So need = {A:1, B:1, C:1} and required = 3. Positions run from 0 (A) to 12 (C).

EventWindowrequiredBest so far
right reaches the C at 5ADOBEC0"ADOBEC" (length 6)
shrink: drop the A at 0, which breaks itDOBEC16
grow until the A at 10DOBECODEBA0still 6 (this one is 10 long)
shrink: drop D, O, then the B at 3 (still valid, because the B at 9 is inside)ECODEBA0still 6 (7 long)
drop E: CODEBA is 6 long, not shorter. Then drop the C at 5, which breaks itODEBA16
grow until the C at 12ODEBANC06
shrink: drop O, D (EBANC, length 5, new best), then EBANC0"BANC" (length 4)
shrink: drop B, which breaks itANC14

The loop ends. The answer is "BANC".

Complexity, derived ​

Let n be the length of s and m the length of t.

Time. Building need reads t once, which is O(m). In the main loop, right moves forward n times. left only moves forward and never passes right, so it moves at most n times in total. Each move does a constant amount of map work, and the validity check is one comparison of required with 0. So the main loop is O(n), and the total is O(n + m).

Space. The two maps hold at most one entry per different letter, which is at most 52 for upper- and lower-case English. That is O(1) for this alphabet, or O(k) for k different characters in general.

Edge cases ​

  • t longer than s. Line (1) returns "".
  • t has a letter that s never has. required never reaches 0, the while loop never runs, and the answer is "".
  • s equals t. The whole string is the only valid window.
  • Repeated letters in t, like "AABC". The counts handle them. A window with only one A never satisfies A.
  • Upper and lower case are different letters. A and a are separate keys.

Variations you will meet ​

This page is the reference version of the shortest valid window.

  • Minimum Size Subarray Sum. Find the shortest stretch of positive numbers whose sum is at least k. The same skeleton, where "valid" means "the running sum is at least k".
  • Substring with Concatenation of All Words. The same counting idea, but over whole words instead of single letters.

Here is the pair worth memorising.

  • Longest valid window: shrink while it is broken, and record after the shrinking loop.
  • Shortest valid window: shrink while it is valid, and record inside the shrinking loop.

Deciding which one a problem wants, before writing anything, is most of the work.

What the interviewer will push on ​

"Why does required count different letters, not total letters?" Because each letter's need is satisfied once, however many copies it needs. Counting total letters would need a different rule and gets tangled.

"Why == and not >= in line (6)?" So that extra copies beyond the need do not lower required again.

"Prove it is O(n)." Both pointers only move forward and never pass each other, so together they make at most 2n moves.

"Does it work when t has repeated letters?" Yes. That is what the counts are for. This question checks whether you used a set by mistake.

"Why do you store the start and length instead of the substring?" Slicing inside the loop would copy letters every time and could make the solution quadratic.

One thing to volunteer: name the two window shapes before you code. "For the longest window I shrink while broken. For the shortest I shrink while valid and record inside the loop. This is the second kind." That tells the interviewer you have a method, not a memorised answer.

Next: 4.6.6 Sliding Window Maximum. A fixed window again, but now you must know its biggest value at every step, which needs a different structure.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet