Skip to content

Min Window Substring

Problem

Given strings s and t, find the minimum window substring of s that contains all characters of t (including duplicates). Return "" if no such window exists.

Approach

Variable-size sliding window with Counter for "need" and "have" tracking. Expand the right pointer to include characters, shrink the left pointer to minimize the window once all characters are satisfied.

When to Use

Minimum window containing all required elements — "smallest substring with all chars", "shortest subarray covering set". Expand right to satisfy, shrink left to minimize. Streaming log/event filtering.

Complexity
Time O(n) where n = len(s) -- each character visited at most twice
Space O(k) where k = number of unique characters in t

Implementation

min_window_substring

Minimum window substring.

Problem

Given strings s and t, find the minimum window substring of s that contains all characters of t (including duplicates). Return "" if no such window exists.

Approach

Variable-size sliding window with Counter for "need" and "have" tracking. Expand the right pointer to include characters, shrink the left pointer to minimize the window once all characters are satisfied.

When to use

Minimum window containing all required elements — "smallest substring with all chars", "shortest subarray covering set". Expand right to satisfy, shrink left to minimize. Streaming log/event filtering.

Complexity

Time: O(n) where n = len(s) -- each character visited at most twice Space: O(k) where k = number of unique characters in t

min_window 

min_window(s: str, t: str) -> str

Return the minimum window in s that contains all chars of t.

min_window("ADOBECODEBANC", "ABC") 'BANC' min_window("a", "a") 'a' min_window("a", "aa") ''

Source code in src/algo/sliding_window/min_window_substring.py 
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
def min_window(s: str, t: str) -> str:
    """Return the minimum window in *s* that contains all chars of *t*.

    >>> min_window("ADOBECODEBANC", "ABC")
    'BANC'
    >>> min_window("a", "a")
    'a'
    >>> min_window("a", "aa")
    ''
    """
    if not t or not s:
        return ""

    need: Counter[str] = Counter(t)
    missing = len(t)
    left = start = end = 0

    for right, ch in enumerate(s, 1):  # right is 1-indexed
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1

        if missing == 0:
            # Shrink from left while window stays valid
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1

            if not end or right - left < end - start:
                start, end = left, right

            # Invalidate window to search for smaller ones
            need[s[left]] += 1
            missing += 1
            left += 1

    return s[start:end]
tests/sliding_window/test_min_window_substring.py
"""Tests for minimum window substring."""

from hypothesis import given
from hypothesis import strategies as st

from algo.sliding_window.min_window_substring import min_window


class TestMinWindow:
    def test_basic(self) -> None:
        assert min_window("ADOBECODEBANC", "ABC") == "BANC"

    def test_single_char_match(self) -> None:
        assert min_window("a", "a") == "a"

    def test_t_longer_than_s(self) -> None:
        assert min_window("a", "aa") == ""

    def test_empty_s(self) -> None:
        assert min_window("", "ABC") == ""

    def test_empty_t(self) -> None:
        assert min_window("ABC", "") == ""

    def test_entire_string_is_window(self) -> None:
        assert min_window("abc", "abc") == "abc"

    def test_duplicate_chars_in_t(self) -> None:
        assert min_window("aabbc", "abc") == "abbc"

    def test_window_at_end(self) -> None:
        assert min_window("xxxxxABC", "ABC") == "ABC"

    @given(
        t=st.text(
            alphabet=st.sampled_from("abc"),
            min_size=1,
            max_size=5,
        ),
    )
    def test_result_contains_all_t_chars(self, t: str) -> None:
        """Any non-empty result must contain all characters of t."""
        from collections import Counter

        s = "aabbccabc"
        result = min_window(s, t)
        if result:
            result_counts = Counter(result)
            for ch, cnt in Counter(t).items():
                assert result_counts[ch] >= cnt

Implement it yourself

Run: just challenge sliding_window min_window_substring

Then implement the functions to make all tests pass. Use just study sliding_window for watch mode.

Reveal Solution

min_window_substring

Minimum window substring.

Problem

Given strings s and t, find the minimum window substring of s that contains all characters of t (including duplicates). Return "" if no such window exists.

Approach

Variable-size sliding window with Counter for "need" and "have" tracking. Expand the right pointer to include characters, shrink the left pointer to minimize the window once all characters are satisfied.

When to use

Minimum window containing all required elements — "smallest substring with all chars", "shortest subarray covering set". Expand right to satisfy, shrink left to minimize. Streaming log/event filtering.

Complexity

Time: O(n) where n = len(s) -- each character visited at most twice Space: O(k) where k = number of unique characters in t

min_window 

min_window(s: str, t: str) -> str

Return the minimum window in s that contains all chars of t.

min_window("ADOBECODEBANC", "ABC") 'BANC' min_window("a", "a") 'a' min_window("a", "aa") ''

Source code in src/algo/sliding_window/min_window_substring.py 
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
def min_window(s: str, t: str) -> str:
    """Return the minimum window in *s* that contains all chars of *t*.

    >>> min_window("ADOBECODEBANC", "ABC")
    'BANC'
    >>> min_window("a", "a")
    'a'
    >>> min_window("a", "aa")
    ''
    """
    if not t or not s:
        return ""

    need: Counter[str] = Counter(t)
    missing = len(t)
    left = start = end = 0

    for right, ch in enumerate(s, 1):  # right is 1-indexed
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1

        if missing == 0:
            # Shrink from left while window stays valid
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1

            if not end or right - left < end - start:
                start, end = left, right

            # Invalidate window to search for smaller ones
            need[s[left]] += 1
            missing += 1
            left += 1

    return s[start:end]