Meta · Coding 1 of 3

Minimum Window Substring

Find the shortest substring of s that contains every character of t.

HardStringSliding windowHash mapBest: O(|s| + |t|) time · O(alphabet) space

Practice question: an editorial practice prompt, not a claim that Meta asks this exact question. Interviews vary by role, level, team, and location.

Problem

Problem statement

Given strings s and t, return the shortest substring of s that contains every character of t, including duplicates. If no such substring exists, return the empty string "".

If t contains a character twice, the window must contain it at least twice. You may assume the shortest window is unique.

Examples

Example 1
Input
s = "ADOBECODEBANC", t = "ABC"
Output
"BANC"

Why: "BANC" is the shortest substring containing A, B and C.

Example 2
Input
s = "a", t = "aa"
Output
""

Why: s has only one "a", so no window works.

Example 3
Input
s = "aa", t = "aa"
Output
"aa"

Constraints

  • 1 ≤ s.length, t.length ≤ 10⁵
  • s and t contain upper- and lower-case English letters.
In the interview

How to answer it out loud

What it tests: Sliding-window reasoning, invariant maintenance, and edge-case testing.

  1. 1
    Clarify

    Clarify character counts and empty input.

  2. 2
    Implement

    Expand until valid, then shrink while preserving validity.

  3. 3
    Verify

    Explain the count invariant and test duplicates.

Approaches

From brute force to the best solution

ApproachIdeaTimeSpace
Check every substringFor each start and end, count characters and test the window.O(n² · k) or worseO(k)
Sliding window with countsBestGrow the right edge until the window is valid, then shrink the left edge while it stays valid.O(|s| + |t|)O(alphabet)
Key insight

Track one number — how many required characters are still missing — so checking validity is O(1). Each index enters and leaves the window at most once, which makes the whole scan linear.

Solution

Reference solution

Each version is self-contained and has been run against the examples and test cases on this page.

from collections import Counter​​def min_window(s: str, t: str) -> str:    need = Counter(t)        # chars still required (goes negative for extras)    missing = len(t)         # required chars not yet inside the window    best_start, best_len = 0, float("inf")    left = 0    for right, ch in enumerate(s):        if need[ch] > 0:            missing -= 1        need[ch] -= 1        while missing == 0:  # window is valid: record it, then shrink from the left            if right - left + 1 < best_len:                best_start, best_len = left, right - left + 1            need[s[left]] += 1            if need[s[left]] > 0:                missing += 1            left += 1    return "" if best_len == float("inf") else s[best_start:best_start + best_len]
Time
O(|s| + |t|)
Space
O(alphabet)
Approach
Sliding window with counts
Test cases

Edge cases to run before you say “done”

InputExpectedWhy it matters
s = "a", t = "b"""No window exists.
s = "aa", t = "aa""aa"Duplicate requirements.
s = "ab", t = "A"""Case matters.
Likely follow-ups

Answer the main question first, then take these on one at a time:

  • Why is it linear?
  • What changes for Unicode?
  • Can memory be bounded?
Avoid these mistakes

Check your recording or written solution against this list:

  • Checking validity by rescanning
  • Mishandling duplicate characters
  • No empty-case handling
Sources and methodology

This guide combines general interview-practice patterns with the public hiring material below. The practice prompt and coaching are PiriPiri AI editorial content, not official Meta questions or answers.

Meta Careers: software engineering full-loop prep ↗
Official sources reviewed 20 September 2026.