Workspace

Problem workspace

3 day streakD

Minimum Window Substring

HardSliding WindowSmallest windows

The challenge

Return the shortest substring of s containing all characters of pattern, including repeated requirements. Return an empty string if none exists; ties keep the earliest window.

Strings contain ASCII characters; indices are zero-based. C++17 or later.

Example

s = ADOBECODEBANC, pattern = ABC → BANC.

Use the walkthrough below to inspect the input and each state change.

See Minimum covering window, step by step

Expand, shrink, and inspect the window state.

13 elements · zero-based indicespattern = ABC
Sliding window over 13 elementsThe current window is empty. Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.Empty window · L = 0, R = -1A0D1O2B3E4C5O6D7E8B9A10N11C12
Current windowRecorded answerOutside window
Left
0
Right
-1
Length
0
Step 01 / 35

Start with an empty window

Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.

left = 0; right = −1

Answer so far

""
View exact input

Input: ["A","D","O","B","E","C","O","D","E","B","A","N","C"] · pattern = ABC

Current window is empty.

Put it into code

Track matched required occurrences, not only distinct letters. An excess copy does not increase matched. Save boundaries while scanning and slice only once.

Indices are zero-based. C++ uses C++17 or later.

from collections import Counter


def min_window(s, pattern):
    if not pattern:
        return ""
    need, count = Counter(pattern), Counter()
    left = matched = start = 0
    best = len(s) + 1
    for right, char in enumerate(s):
        count[char] += 1
        if count[char] <= need[char]:
            matched += 1
        while matched == len(pattern):
            if right - left + 1 < best:
                start, best = left, right - left + 1
            old = s[left]
            if count[old] <= need[old]:
                matched -= 1
            count[old] -= 1
            left += 1
    return "" if best == len(s) + 1 else s[start:start + best]

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap