Sliding window for minimum window substring in Python

Expand the right pointer until the window is valid, then shrink the left pointer while it stays valid; O(n + m) time.

File: minimum_window_substring_algorithm.py, 32 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

minimum_window_substring_algorithm.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/minimum-window-substring-algorithm/. The authors are listed in prov/380AMB.jsonl.

from collections import Counter


def min_window(s: str, t: str) -> str:
    """Return the leftmost shortest substring of s that contains every character of t
    with at least its multiplicity in t, or "" if there is none (or if t is empty).

    Cost: O(len(s) + len(t)) expected time, O(len(t)) extra space.
    """
    if not t:
        return ""
    need = Counter(t)  # @line L1
    missing = len(t)
    left = 0
    best_len, best_start = len(s) + 1, 0
    for r, c in enumerate(s):  # @line L2
        if need[c] > 0:  # @line L3
            missing -= 1
        need[c] -= 1  # @line L4
        while missing == 0:  # @line L5
            if r - left + 1 < best_len:  # @line L6
                best_len, best_start = r - left + 1, left
            need[s[left]] += 1  # @line L7
            if need[s[left]] > 0:  # @line L8
                missing += 1
            left += 1  # @line L9
    if best_len > len(s):  # @line L10
        return ""
    return s[best_start : best_start + best_len]

test_minimum_window_substring_algorithm.py 43 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/minimum-window-substring-algorithm/. The authors are listed in prov/380AMB.jsonl.

import random
from collections import Counter

from minimum_window_substring_algorithm import min_window


def brute(s: str, t: str) -> str:
    need = Counter(t)
    best = None
    for i in range(len(s)):
        for j in range(i, len(s)):
            have = Counter(s[i : j + 1])
            if all(have[c] >= k for c, k in need.items()):
                if best is None or j - i + 1 < best[0]:
                    best = (j - i + 1, i)
                break
    return "" if best is None else s[best[1] : best[1] + best[0]]


def test_example() -> None:
    assert min_window("ADOBECODEBANC", "ABC") == "BANC"


def test_edges() -> None:
    assert min_window("a", "a") == "a"
    assert min_window("a", "aa") == ""
    assert min_window("aa", "aa") == "aa"
    assert min_window("", "a") == ""
    assert min_window("abc", "") == ""
    assert min_window("AAB", "AB") == "AB"
    assert min_window("abcab", "ab") == "ab"
    assert min_window("xyz", "q") == ""


def test_against_brute_force() -> None:
    rng = random.Random(20261104)
    for _ in range(2000):
        s = "".join(rng.choice("abcd") for _ in range(rng.randrange(0, 14)))
        t = "".join(rng.choice("abcd") for _ in range(rng.randrange(1, 5)))
        assert min_window(s, t) == brute(s, t)

What the next level needs

the tests did not run in this build

Read the full page about Sliding window for minimum window substring