LeetCode 76: Minimum Window Substring — Python Solution

LeetCode 76: Minimum Window Substring is a hard sliding-window problem. The useful idea is to track the characters that are still missing, rather than rescanning the current window every time its left edge moves. This walkthrough derives that invariant, gives a linear-time Python implementation, and tests the cases that usually expose counting bugs.

This independent guide paraphrases the task rather than reproducing LeetCode’s prompt. Use the official page for the exact statement, examples, constraints, and submission runner.

Difficulty	Hard
Pattern	Variable-size sliding window
State	Required counts plus one total missing-count
Complexity	O(|s| + |t|) time, O(k) auxiliary space

The invariant that makes the window work

Let need[c] represent how many more copies of character c the current window would need. Before scanning, it is simply the frequency table for t. When a character enters the window, decrement its counter. A positive value before that decrement means the new character filled a real requirement, so decrement missing as well.

Surplus characters naturally become negative. That is useful: when the left edge removes a surplus copy, the counter moves toward zero without making the window invalid. The window is valid exactly when missing == 0; at that point, move the left edge forward as far as possible and record the shortest valid range seen so far.

Python solution

from collections import Counter


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

        need = Counter(t)
        missing = len(t)
        left = 0
        best_start = 0
        best_length = float("inf")

        for right, char in enumerate(s):
            # A positive counter means this occurrence was still needed.
            if need[char] > 0:
                missing -= 1
            need[char] -= 1

            # The window is valid; shrink it until removing one more
            # character would make it invalid.
            while missing == 0:
                length = right - left + 1
                if length < best_length:
                    best_start = left
                    best_length = length

                leaving = s[left]
                need[leaving] += 1
                if need[leaving] > 0:
                    missing += 1
                left += 1

        if best_length == float("inf"):
            return ""
        return s[best_start:best_start + best_length]

Tracing the two-pointer decisions

The right pointer expands the window one character at a time. It never moves backward. Once every required character is present, the left pointer removes characters until the window is invalid again. It also never moves backward, so each character is added once and removed at most once.

For s = "ADOBECODEBANC" and t = "ABC", the first valid window is "ADOBEC". Shrinking cannot remove A, B, or C without breaking validity, so the algorithm stores it and continues expanding. Later it finds "BANC", then proves that no shorter valid suffix exists before continuing. The answer is therefore "BANC".

Why repeated characters are the common bug

A target such as "AABC" needs two copies of A, not merely the presence of the character. A boolean set cannot represent that requirement. The frequency counter can: the first A moves its counter from 2 to 1, the second moves it from 1 to 0, and any later A becomes surplus with a negative counter. The same logic works when those copies leave the window.

Correctness argument

1. Invariant. At every point, need[c] is the number of additional copies of c required by the current window; negative values represent surplus copies.
2. Validity. missing counts required character occurrences still absent from the window, so missing == 0 exactly when the window contains t.
3. Minimality for each right edge. When a window becomes valid, the inner loop removes characters until the next removal would make it invalid. The stored range is therefore the shortest valid window ending at that right edge.
4. Global result. Every right edge is visited, so comparing those per-edge minima yields the shortest valid window overall.

Complexity

Building the frequency table takes O(|t|) time. The right pointer makes |s| advances, and the left pointer makes at most |s| advances, so the complete scan is O(|s| + |t|) time. The counter stores at most one entry per distinct character, giving O(k) auxiliary space where k is the number of distinct characters in the inputs.

Regression tests and edge cases

These checks cover the normal case, repeated requirements, an impossible target, and the case where the best window is the entire input:

solution = Solution()
assert solution.minWindow("ADOBECODEBANC", "ABC") == "BANC"
assert solution.minWindow("a", "a") == "a"
assert solution.minWindow("a", "aa") == ""
assert solution.minWindow("aa", "aa") == "aa"
assert solution.minWindow("a", "b") == ""
assert solution.minWindow("ab", "b") == "b"

• Do not replace the frequency table with a set when the target contains duplicates.
• Update the counter before moving the left pointer; otherwise the algorithm can lose track of the character that made the window invalid.
• Return an empty string when no valid window exists, rather than returning the last examined range.
• Python strings and Counter handle Unicode characters too; the invariant does not depend on an ASCII-only alphabet.

---

For adjacent sliding-window patterns, compare this solution with Longest Substring Without Repeating Characters, Minimum Size Subarray Sum, and Substring with Concatenation of All Words. The LeetCode Python solutions hub collects the rest of the tested study set.

This article is part of the LeetCode Python solutions study guide.