minimum_window_substring.py

from collections import Counter, defaultdict


class Solution:
    """LeetCode #76 - Minimum Window Substring (Hard)
    https://leetcode.com/problems/minimum-window-substring/

    Return the shortest substring of `s` that contains every character of `t`,
    including duplicates. Order does not matter. If no such window exists,
    return "".
    """

    def minWindow(self, s: str, t: str) -> str:
        """Sliding window that grows on the right and shrinks on the left.

        The window is only ever *valid* or *invalid*, so the loop has a simple
        shape: extend right until valid, then shrink left as far as validity
        survives, recording the best length each time.

        The trick that keeps it O(n) is the `satisfied` counter. Comparing the
        whole window map against `need` on every step would cost O(alphabet)
        per character; instead we track how many *distinct* characters have
        reached their required count, and update that counter only at the exact
        moment a character crosses its threshold:

            window[ch] == need[ch]   ->  one more character satisfied
            window[ch] <  need[ch]   ->  one fewer (only right after removal)

        Note the strict `==` / `<`. Using `>=` would re-count a character every
        time an extra copy arrives, which silently breaks the counter.

        Time:  O(len(s) + len(t)) - each index enters and leaves the window once.
        Space: O(len(t)) for the two maps (bounded by the alphabet).
        """
        if not s or not t or len(t) > len(s):
            return ""

        need = Counter(t)
        required = len(need)          # distinct characters we must cover
        window = defaultdict(int)
        satisfied = 0

        best_len = float("inf")
        best_start = 0
        left = 0

        for right, ch in enumerate(s):
            window[ch] += 1
            if ch in need and window[ch] == need[ch]:
                satisfied += 1

            # Window is valid - shrink it while it stays valid.
            while satisfied == required:
                if right - left + 1 < best_len:
                    best_len = right - left + 1
                    best_start = left

                dropped = s[left]
                window[dropped] -= 1
                if dropped in need and window[dropped] < need[dropped]:
                    satisfied -= 1        # this removal is what broke validity
                left += 1

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