Skip to main content
Advanced

Minimum Window Substring

hardHard arrays and strings Must-doMetaGoogleDatadog

Problem statement

You're given two strings, s and t. Find the shortest contiguous piece of s — a substring — that contains every character in t, including repeats. For example, if t has two 'a's, the window has to contain at least two 'a's somewhere inside it, not just one.

Return that shortest window as a string. If no window of s contains everything t needs, return an empty string instead. It's guaranteed that whenever an answer exists, there's only one shortest window (no ties to break).

Examples

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

Explanation: "BANC" is the shortest substring of s that contains at least one 'A', one 'B' and one 'C'.

Example 2

Input: s = "a", t = "a"

Output: "a"

Explanation: The entire string s is already the shortest (and only) window that contains everything t needs.

Example 3

Input: s = "a", t = "aa"

Output: ""

Explanation: t needs two 'a's, but s only has one character total, so no window of s can ever satisfy the requirement.

Hints

Hint 1: Checking whether a candidate window already contains everything t needs comes down to comparing two counts per character: how many of that character the window currently has, versus how many t needs.

Approach

Optimal: Sliding window with two pointers

Intuition

The brute force approach restarts its window from scratch at every starting index, throwing away all the counting work it just did the moment it moves to the next one. A window whose left and right edges only ever move forward — never backward, and never reset — avoids that waste: expand the right edge until the window contains everything t needs, then shrink the left edge as far as possible while the window stays valid, recording the window's length each time it's still valid. Because both edges only move forward, the whole string is scanned just once in total, not once per starting index.

Instead of checking "does every character have enough count?" from scratch every time, keep a single running counter: formed, the number of distinct characters in t whose required count is currently met inside the window. The window is valid exactly when formed equals the number of distinct characters t needs — a single number comparison, not a full re-check of every character.

Steps

  1. Count how many of each character t requires (need), and note how many distinct characters that is (required).
  2. Keep a running count of characters currently in the window (windowCount), and a counter formed for how many distinct required characters are currently fully satisfied.
  3. Move the right edge forward one character at a time: add that character to windowCount, and if its count just reached exactly what's needed, increment formed.
  4. Whenever formed == required (the window is currently valid), repeatedly try shrinking from the left: record the window's length if it's the best seen so far, then remove the leftmost character from windowCount and move the left edge forward — decrementing formed if that removal just made some character's count fall below what's needed.
  5. Once the right edge has scanned the whole string, return the shortest valid window recorded, or an empty string if none was found.

Dry run

s = "ADOBECODEBANC", t = "ABC" (need = {A:1, B:1, C:1}, required = 3)

right reaches window formed shrinking? best window so far
index 5 ('C') "ADOBEC" 3 (valid) shrink left from 0 → 4 (loses 'A') "ADOBEC" (len 6)
index 9 ('B') "CODEB" then extends building back toward 3 — "ADOBEC" (len 6)
index 12 ('C') "BANC" 3 (valid) shrink left, window stays "BANC" "BANC" (len 4)

The window "BANC" is found once the right edge reaches the final 'C', and shrinking from the left can't make it any smaller without losing a required character, so it becomes the final answer — matching the expected output, and matching what the brute force approach found, but without ever restarting the scan.

Edge cases: when s = "a", t = "aa", formed can never reach required (there's only one 'a' available but two are needed), so the window is never valid and an empty string is correctly returned. Because both left and right only ever move forward, the total work is proportional to the combined length of s and t, not to the length of s squared.

Complexity

Time O(m + n) - building the required counts from t is O(n), and the right and left pointers each move forward at most m times total across the whole scan of s, with O(1) work at each step, giving a combined O(m + n). This matches the O(m + n) bound the problem's own follow-up asks for.

Space O(n) - the need and windowCount maps both scale with the number of distinct characters involved, not with the length of s.

from collections import Counter


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

        need = Counter(t)
        required = len(need)  # number of distinct characters that must be satisfied
        window_count = Counter()
        formed = 0  # number of distinct characters currently satisfied

        best_len = float("inf")
        best_left = 0
        left = 0

        for right, char in enumerate(s):
            window_count[char] += 1
            if char in need and window_count[char] == need[char]:
                formed += 1

            while formed == required:
                if right - left + 1 < best_len:
                    best_len = right - left + 1
                    best_left = left

                left_char = s[left]
                window_count[left_char] -= 1
                if left_char in need and window_count[left_char] < need[left_char]:
                    formed -= 1
                left += 1

        return "" if best_len == float("inf") else s[best_left:best_left + best_len]


if __name__ == "__main__":
    print(Solution().minWindow("ADOBECODEBANC", "ABC"))  # "BANC"
    print(Solution().minWindow("a", "a"))                # "a"
    print(Solution().minWindow("a", "aa"))                # ""
RecapThe whole problem in a few lines, for the night before
  • Spot it: "shortest/smallest window containing all of X" (with duplicates counted) inside a longer string
  • Idea: sliding window with two pointers — expand right until the window is valid, then shrink left as far as possible while it stays valid, tracking a single formed counter instead of re-checking every character
  • Cost: O(m + n) time, O(n) space (trying every starting index fresh is O(m^2 · n))
  • Trap: resetting the window's character counts back to empty for every new starting index instead of letting left and right both only move forward — that's what turns an O(m + n) scan back into an O(m^2) one

Interview follow-ups

  • What if s and t could contain a much larger character set, such as full Unicode, instead of just English letters?

    The same sliding window logic applies unchanged — only the choice of data structure for need and windowCount would need to switch from something sized for a fixed small alphabet (like a 128-entry array) to a general hash map, since the character set is no longer small and bounded.

  • What if you needed to return every minimal window of this length, not just one?

    Once the single shortest length is known from a first pass, run the sliding window logic again (or track matches during the same pass) and record every window whose length equals that shortest length, rather than only ever keeping a single best answer.

Frequently asked questions

Moving right forward is how new characters ever get considered, and moving left forward is how a window that's already valid gets tested to see if it can be made smaller — neither pointer ever benefits from revisiting territory it has already passed, since a substring is uniquely defined by its left and right positions moving in one direction. That's exactly why the whole string only needs to be scanned once.

Checking every character in need on every step would cost time proportional to the number of distinct characters in t, on top of the work already being done — for a t with many distinct characters, that adds up. Tracking a single count of how many characters are currently satisfied turns that repeated check into one quick number comparison instead.

Finding the smallest contiguous window of log lines, requests, or events that contains a required set of markers — every error code in a checklist, say — is a direct real-world version of this exact search, and the shrink-while-valid sliding window technique is the standard efficient tool for it.

Only the counts matter — the window just needs to contain at least as many of each required character as t has, wherever they happen to sit inside the window. This is why the solution counts characters in t rather than trying to match t as a contiguous or ordered pattern.