Solving Minimum Window Substring

Count how many times each character is needed, then slide a window over the source while tracking how many of those requirements are currently satisfied. Extend the window to the right. Whenever every requirement is satisfied, start shrinking from the left, recording the window length each time it improves, and keep shrinking until the window stops satisfying the requirements.

from collections import Counter

def min_window(s, t):
    if not s or not t or len(t) > len(s):
        return ""
    need = Counter(t)
    window = Counter()
    left = 0
    formed = 0
    best = (float("inf"), 0, 0)
    for right, char in enumerate(s):
        window[char] += 1
        if char in need and window[char] == need[char]:
            formed += 1
        while formed == len(need):
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            outgoing = s[left]
            window[outgoing] -= 1
            if outgoing in need and window[outgoing] < need[outgoing]:
                formed -= 1
            left += 1
    return "" if best[0] == float("inf") else s[best[1]:best[2] + 1]

print(min_window("ADOBECODEBANC", "ABC"))
print(min_window("a", "aa"))

The outputs are BANC and an empty string. The window from index nine to twelve contains the A, the B and the C, and no shorter run does. The second call asks for two a characters from a source that has only one, so no window can ever satisfy the requirement and the function returns an empty string.

The mechanism is the formed counter. It counts how many distinct required characters are currently present in sufficient quantity, and it only moves when a count reaches exactly the required amount or falls below it. Counting distinct requirements rather than individual characters is what makes repeated letters in the target work correctly: for a target of aab you need two a characters and one b, and the counter tracks those three requirements separately.

The trade-off to name is that the algorithm is a sliding window with two pointers and two counters, so the space is O of the alphabet size and the time is O of the sum of the two string lengths. Each pointer moves in one direction only, which is what keeps it linear. The alternative, generating every substring and testing it, is cubic in the worst case and is the mistake this problem is designed to expose.

It returns an empty string, because no window can ever satisfy the requirement. The loop extends the right edge across the whole source, the formed counter never reaches the number of requirements, so the shrinking loop never runs once, and the best window is never updated.

def min_window(s, t):
    need = {}
    for char in t:
        need[char] = need.get(char, 0) + 1
    missing = len(t)
    left = 0
    best = (float("inf"), 0, 0)
    for right, char in enumerate(s):
        if char in need:
            need[char] -= 1
            if need[char] == 0:
                missing -= 1
        while missing == 0:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            outgoing = s[left]
            if outgoing in need:
                need[outgoing] += 1
                if need[outgoing] > 0:
                    missing += 1
            left += 1
    if best[0] == float("inf"):
        return ""
    return s[best[1]:best[2] + 1]

print(min_window("ADOBECODEBANC", "ABC"))
print(min_window("a", "aa"))

The outputs are BANC and an empty string. This version counts missing character occurrences rather than satisfied requirements, which is the other common formulation of the same algorithm. The missing counter starts at the length of the target and drops each time a needed character arrives in sufficient quantity, then rises again when the left edge removes one that was needed.

Returning an empty string rather than None is a deliberate choice about the contract. The empty string is the natural answer for a string problem, since the shortest valid substring of a source that cannot contain the target has length zero. Whichever convention you pick, it is worth stating it out loud, because a caller that expects None and receives an empty string will silently take a different branch.

The trade-off to name is that this formulation needs a guard for the empty target, because with an empty target the missing counter starts at zero and the shrinking loop would advance the left edge past the end of the string. The other formulation, which counts satisfied requirements, handles that case more gracefully, and both are linear in time and use space proportional to the alphabet. Mentioning that edge case is the kind of detail that separates a complete answer from a working one.

Track the best window as a triple of length, start index and end index, and only update it when a strictly shorter valid window is found. At the end, slice the source using the recorded indices.

from collections import Counter

def min_window_detail(s, t):
    need = Counter(t)
    window = Counter()
    left = 0
    formed = 0
    best = (float("inf"), 0, 0)
    for right, char in enumerate(s):
        window[char] += 1
        if char in need and window[char] == need[char]:
            formed += 1
        while formed == len(need):
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            outgoing = s[left]
            window[outgoing] -= 1
            if outgoing in need and window[outgoing] < need[outgoing]:
                formed -= 1
            left += 1
    if best[0] == float("inf"):
        return "", 0
    return s[best[1]:best[2] + 1], best[0]

print(min_window_detail("ADOBECODEBANC", "ABC"))

The output is the tuple BANC and 4. Recording indices rather than the substring itself is the right choice because slicing inside the loop would allocate a new string on every improvement, turning an otherwise linear algorithm into one that copies repeatedly.

The best-candidate bookkeeping is where the subtle bugs live. The length must be computed as right minus left plus one, the inclusive width of the window, and the comparison must be strict so that a later window of the same length does not overwrite an earlier one, which keeps the result deterministic. The sentinel of infinite length is what lets you compare against a best that has never been set, and the final check for that sentinel is what distinguishes no solution from a solution of length zero.

The trade-off to name is that storing indices costs two extra integers and requires the caller to still have access to the original string. If the caller only wants the length, you can skip the slice entirely. If you want every valid window rather than only the shortest, you would collect all of them, and the output size changes the complexity from linear in the input to linear in the number of windows.