Minimum Window Substring

Hints

1. Work out which direction validity is monotone. Adding a character can only help coverage; removing one can only hurt. So valid windows are upward-closed: any superset of a valid window is valid. That tells you the loop shape, expand to reach validity then shrink while validity survives.
2. Count duplicates, do not just track presence. t = "aa" requires two as. A set of required characters answers the wrong question and accepts s = "a". Build a frequency map of t.
3. Record the answer before shrinking, not after. Inside the shrink loop the window is valid at the top of each iteration. Measure there. Measuring after the removal records a window you have already broken.
4. Replace the map comparison with a counter. Let required be the number of distinct characters in t and formed the number currently satisfied. The window is valid exactly when formed == required, which is one integer comparison instead of scanning a map.
5. Update the counter only on threshold crossings. Increment formed when a character's window count becomes exactly equal to its requirement, and decrement when it drops below. Testing for equality rather than "greater or equal" is what keeps surplus copies from inflating the count.
6. Let characters outside t ride along harmlessly. They are counted in the window map but never appear in the requirement map, so they never touch formed. They still get shrunk away, which is how "ADOBEC" narrows to "BANC".

Solution: two approaches

Approach 1 - Check every window: O(m^2 * k) time

The definition, made literal, and the baseline the optimisation is measured against.

from collections import Counter

def min_window_brute(s, t):
    need = Counter(t)
    best = ""
    for i in range(len(s)):
        for j in range(i, len(s)):
            window = Counter(s[i:j + 1])
            if all(window[c] >= need[c] for c in need):
                if not best or j - i + 1 < len(best):
                    best = s[i:j + 1]
                break                     # shortest window from this start
    return best

There are Theta(m^2) windows and each containment check costs O(k) over the distinct characters of t, on top of rebuilding the counter. At m = 10^5 this is hopeless, but it pins down the specification exactly: a window qualifies when every required character appears at least as often as required, and surplus characters are irrelevant. Keep it as an oracle for randomised testing against the fast version. The break after the first valid window is the one piece of insight this version does contain: once a window starting at i is valid, extending it further can only make it longer, so the shortest window from that start is found immediately and the inner loop can stop. That is already the seed of the real algorithm, which keeps the same idea while refusing to restart the scan for every value of i. When you are stuck on a window problem, writing the quadratic version and then asking which part of its work is repeated between adjacent starting positions reliably produces the linear one.

Approach 2 - Sliding window with a satisfaction counter: O(m + k) time, O(m + k) space

The answer. Two monotone pointers and one integer standing in for a map comparison.

from collections import Counter

def min_window(s, t):
    if not s or not t:
        return ""

    need = Counter(t)
    required = len(need)          # distinct characters that must be satisfied
    window = {}
    formed = 0                    # how many of those are currently satisfied
    left = 0
    best = (float('inf'), 0, 0)   # (length, start, end inclusive)

    for right, ch in enumerate(s):
        window[ch] = window.get(ch, 0) + 1
        if ch in need and window[ch] == need[ch]:
            formed += 1

        while left <= right and formed == required:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            lch = s[left]
            window[lch] -= 1
            if lch in need and window[lch] < need[lch]:
                formed -= 1
            left += 1

    return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]

Why formed is a faithful proxy for validity: it counts the distinct required characters whose window count has reached the requirement. It is incremented exactly when some count rises to meet its threshold and decremented exactly when one falls below, so it always equals the number of satisfied requirements. The window is valid precisely when every requirement is satisfied, which is formed == required. The predicate that cost O(k) now costs one comparison, and the updates that maintain it are O(1) each.

Why the equality test, not a comparison: if the test were window[ch] >= need[ch], a character needed twice and present five times would increment formed on occurrences two through five, pushing it past required and making every subsequent window look valid. The equality fires exactly once per crossing, on the way up, and its mirror window[lch] < need[lch] fires exactly once on the way down. Transitions, not states.

Why recording happens at the top of the shrink loop: the loop is entered only when the window is valid, and the removal at the bottom may destroy that validity. Measuring first captures the smallest valid window ending at the current right. Moving the measurement below the removal records a window that is one character shorter and possibly invalid, which produces answers that are too short and do not contain t.

Why it is linear despite the nested loop: right advances exactly m times across the whole run. left only ever advances and is bounded by m, so the inner loop body executes at most m times in total, not per outer iteration. Every character is added once and removed at most once, giving at most 2m pointer moves plus O(k) to build the requirement map. The nesting is syntactic, not asymptotic, and stating this amortised argument out loud is expected.

Why the answer is stored as indices: slicing the string every time a shorter window is found would cost O(m) per improvement and could total O(m^2). Storing a length and two indices costs O(1) per improvement, with a single slice at the end. Note the stored right index is inclusive while Python slicing is exclusive, hence best[2] + 1.

Trace on s = "ADOBECODEBANC", t = "ABC"

Complexity comparison

Edge cases to verify

• No valid window: s = "a", t = "aa" returns "". formed never reaches required and the sentinel length survives.
• Whole string is the answer: s = "abc", t = "cba" returns "abc". The shrink loop runs once and immediately breaks validity.
• Duplicates in t: s = "aab", t = "aab" returns "aab". This is the case that fails when a set replaces the counter.
• Surplus copies: s = "aaaab", t = "ab" returns "ab". Catches an over-eager formed increment.
• Case sensitivity: s = "AB", t = "ab" returns "". Upper and lower case are distinct characters.

Where beginners go wrong

• Incrementing formed on every occurrence. The update must fire only when a count reaches its requirement exactly. Using >= lets surplus copies push formed past required, after which every window reports valid and the algorithm returns a substring that does not cover t.
• Using a set of required characters. Presence is not enough when t contains duplicates. t = "aa" needs two as, and a set-based solution happily accepts s = "a".
• Re-scanning the window to test validity. Comparing two frequency maps on every pointer move costs O(k) each time and turns a linear algorithm into O(m * k). The counter exists precisely to avoid this.
• Recording the best window after the removal. Inside the shrink loop the window is valid at the top and possibly invalid at the bottom. Measure before you remove, or you will return windows one character too short.
• Off-by-one on the final slice. The stored right index is inclusive while Python slicing is exclusive, so the answer is s[start:end + 1]. Dropping the + 1 truncates the last character, which produces an almost-right answer that passes on inputs where the final character is a duplicate.
• Special-casing characters not in t. No branch is needed. They accumulate in the window map, never appear in the requirement map, and so never touch formed. The ch in need guard on the update is the only thing required.

Interview follow-ups to expect

• "The alphabet is Unicode, not 52 ASCII letters." Nothing changes structurally, since the maps are already hash-based. The space bound becomes O(distinct characters) rather than a constant, which is worth stating rather than glossing over.
• "Return all minimum windows, not just one." Keep a list and reset it when a strictly shorter window appears, append when an equal-length one does. Careful: the count of such windows can be large, so the output is no longer O(m).
• "Find the minimum window containing t as a subsequence, in order." Different problem. The window now has to preserve order, so the counter approach does not apply. A two-pointer forward-then-backward scan solves it in O(m * k), and a DP over positions does better when k is large.
• "Find the longest substring with at most k distinct characters." Same skeleton, opposite monotonicity: shrink while the window holds more than k distinct characters and record after each repair. Being able to explain why the record-and-shrink order flips is the point of the comparison.
• "Permutation in string: does s contain any permutation of t?" A fixed-size window of length len(t) with the same satisfaction counter. Because the size is fixed, you slide rather than shrink, and the answer is a boolean.
• "Can you use less memory?" With a known alphabet, replace both hash maps with fixed arrays of 128 counters. Same asymptotics, much better constants, and the counter logic is unchanged.

Related reading

• The Sliding Window: the template, and how the direction of monotonicity decides the loop shape.
• Frequency Counting: why tracking threshold crossings beats recomputing an aggregate.
• Longest Substring Without Repeating Characters: the mirror problem, where the window is maximised and validity is downward-closed.