Minimum Window Substring

The hard part is not moving two pointers. It is preserving the target’s multiplicity while the window changes.

A set-based solution sees t = "AAB" as {A, B} and accepts a window containing one A. That window is wrong. The contract is frequency-based: the window needs two As and one B.

The reliable model is:

1. Expand the right boundary until the window satisfies every required count.
2. Record the current valid window.
3. Shrink from the left while validity survives.
4. Keep the shortest valid window seen.

The key state is a pair of frequency maps plus one counter that makes validity constant-time.

Read the Contract Precisely

Given strings s and t, return the shortest contiguous substring of s containing every character in t at least as many times as it appears in t. If no such substring exists, return "".

The characters are case-sensitive. Uppercase and lowercase letters are different requirements.

For example:

s = "AABXBC"
t = "AAB"

A valid answer must contain:

• two copies of 'A'
• one copy of 'B'

The window "AB" is invalid even though it contains every distinct character from t. This is the failure mode that rules out a plain set.

The stated lengths can reach 10^5, so checking every substring independently is too expensive. There are O(m^2) possible substrings in s, where m = len(s), and repeatedly counting their contents adds more work. We need to reuse the count information as the window moves.

The answer is guaranteed to be unique in the canonical problem, so there is no tie-breaking decision to make. The implementation still needs explicit best-window tracking because it discovers candidates incrementally.

Recognize Expand Then Shrink

This is a sliding-window minimization problem. Three structural signals point to that pattern:

• The candidate is a contiguous interval [left, right].
• Validity is defined by lower bounds on character frequencies.
• The objective is to minimize the interval length.

The window grows when it is missing required characters. Once it becomes valid, growth is no longer useful for the current right boundary; removing unnecessary material may produce a shorter answer.

That gives the control rule:

Expand until valid. Shrink until invalid. Then expand again.

This is different from the longest-substring problem where the window is repaired when it violates a restriction, such as containing a repeated character. Here, the window begins incomplete and becomes valid only after accumulating enough evidence.

It is also different from a last-seen jump. A character’s most recent position does not tell us whether the window contains enough copies of every required character. We need mutable frequency state.

Prefix sums are not the natural lens either. Prefix sums are useful when a fixed cumulative quantity answers range queries. Here, the relevant question is whether the current interval has crossed several character-specific thresholds. As left advances, counts must be removed and their threshold effects observed.

Define the Window State

Let:

• need[c] be the number of copies of character c required by t.
• window[c] be the number of copies of c currently inside s[left:right + 1].
• required be the number of distinct characters in need.
• formed be the number of distinct required characters whose current count has reached its target.

For t = "AAB":

need = {'A': 2, 'B': 1}
required = 2

A window with counts A: 2, B: 1 has formed == required, so it is valid.

A window with counts A: 3, B: 1 is also valid. The extra A is surplus; it does not create a new requirement.

A window containing A: 2, B: 0 has only one satisfied requirement, so formed == 1, not 2.

The important transitions are exact threshold crossings:

When adding a character

Suppose the right pointer adds character c.

window[c] += 1

If c is required and window[c] == need[c], then this addition completes one distinct requirement:

formed += 1

Do not increment formed for every matching copy. If need['A'] == 2, the first A is progress toward the threshold, but only the second A changes the status from unsatisfied to satisfied.

When removing a character

Suppose the left pointer removes character c.

After decrementing its count, the requirement is broken only if:

window[c] < need[c]

Equivalently, before decrementing, the count was exactly at its required threshold. Then:

formed -= 1

Removing a surplus copy does not affect validity. Removing an irrelevant character does not affect validity. Removing a required character from an already-underfilled count cannot happen while the loop is shrinking a valid window, because the loop stops as soon as validity breaks.

Invariant: formed counts satisfied distinct requirements, not matched characters and not total characters.

That distinction is the whole algorithm. Get it wrong and repeated characters quietly corrupt the result.

Build the Algorithm

The scan has one outer movement and one inner contraction.

1. Build need from t.
2. Set left = 0, formed = 0, and empty window counts.
3. Move right from left to right across s.
4. Add s[right] to the window and update formed if a threshold is crossed.
5. While formed == required:
   • record the current valid window if it is shorter than the best one;
   • remove s[left];
   • update formed if that removal breaks a threshold;
   • advance left.
6. Return the recorded slice, or "" if no valid window was found.

Recording must happen before removing the left character. The current window is valid at that point. After removal, it may be invalid, and that invalid state is not a candidate.

The algorithm does not construct a substring on every iteration. It stores best_start and best_length, then slices s once at the end. That keeps the state focused and avoids repeated copying during the scan.

Prove the Greedy Shrink

The inner loop is greedy, but it is not a guess. Its behavior follows from the validity condition.

Fix a particular right endpoint. Once the window [left, right] becomes valid, moving left rightward can only remove characters. It cannot add missing characters. Therefore, as we shrink from the left, validity can persist for a while and then fail at the first removal that takes a required count below its threshold.

At the start of each inner-loop iteration:

• the current window is valid;
• formed == required;
• the current left and right identify a legitimate candidate.

We record that candidate, remove s[left], and advance left.

After the move, exactly one of two things is true:

1. The window remains valid, so another contraction may improve it.
2. The window becomes invalid because a required threshold was broken, so this right boundary cannot produce a shorter valid window by moving left farther.

For this fixed right, the last valid window before failure is therefore minimal among all valid windows ending at right. Any earlier left boundary creates a window at least as long.

The outer loop examines every possible right boundary. Since the globally shortest valid substring ends at some right boundary, and we find the shortest valid candidate for that boundary, keeping the best candidate globally gives the correct answer.

The order of operations matters:

valid window
→ record it
→ remove the left character
→ possibly become invalid

If you remove first and record afterward, you can skip the shortest valid window. The invalid post-removal state is evidence that the previous state was the boundary you needed to save.

Trace Counts on ADOBECODEBANC

Use:

s = "ADOBECODEBANC"
t = "ABC"

The required map is:

need = {'A': 1, 'B': 1, 'C': 1}
required = 3

The first time all three requirements are satisfied, the window is "ADOBEC". It is valid, but it contains unnecessary characters. Shrinking exposes that fact.

Event	Window	formed	Valid?	Best
Add C at index 5	ADOBEC	3	yes	ADOBEC
Remove A at index 0	DOBEC	2	no	ADOBEC
Add later A at index 10	CODEBA	2	no	ADOBEC
Add N at index 11	CODEBAN	2	no	ADOBEC
Add C at index 12	CODEBANC	3	yes	ADOBEC
Remove C at index 5	ODEBANC	3	yes	ADOBEC
Remove O at index 6	DEBANC	3	yes	ADOBEC
Remove D at index 7	EBANC	3	yes	ADOBEC
Remove E at index 8	BANC	3	yes	BANC
Remove B at index 9	ANC	2	no	BANC

Several details are doing real work here:

• O, D, E, and N are irrelevant to validity, but they still contribute to window length.
• The later C at index 12 makes a new valid window.
• Removing irrelevant characters preserves formed.
• Removing B from "BANC" breaks the requirement, so shrinking stops.
• "BANC" is recorded before that final removal.

A common bug is to update the answer only after removing s[left]. That would miss "BANC" because the removal of B produces the invalid window "ANC".

Implement the Python Solution

Counter expresses the frequency model directly. The threshold conditions remain explicit, which is more valuable in an interview than compressing the logic into a clever one-line test.

from collections import Counter


def min_window(s: str, t: str) -> str:
    need = Counter(t)
    required = len(need)

    window = Counter()
    formed = 0

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

    for right, char in enumerate(s):
        window[char] += 1

        # This character satisfies a distinct requirement exactly now.
        if char in need and window[char] == need[char]:
            formed += 1

        # The current window is valid. Record it before removing from
        # the left, because the removal may break validity.
        while formed == required:
            current_length = right - left + 1

            if current_length < best_length:
                best_start = left
                best_length = current_length

            left_char = s[left]
            window[left_char] -= 1

            # The removal dropped a required count below its threshold.
            if left_char in need and window[left_char] < need[left_char]:
                formed -= 1

            left += 1

    if best_length == float("inf"):
        return ""

    return s[best_start:best_start + best_length]

Every variable has a correctness job:

• need defines the target multiset.
• window represents the current interval.
• required counts distinct obligations.
• formed tells us whether all obligations are currently satisfied.
• left and right define the active interval.
• best_start and best_length preserve the shortest valid interval without repeatedly copying strings.

The no-window sentinel is float("inf") for best_length. That is safer than using 0, because a valid window has positive length under the problem constraints. If the sentinel survives the scan, no valid interval was found.

A fixed-size array indexed by character code is also valid under the stated uppercase/lowercase English alphabet. I prefer maps here because they expose the multiplicity model and generalize without changing the reasoning. If the alphabet is fixed and implementation overhead matters, arrays can make the same transitions slightly more compact.

Cost, Edge Cases, and Failure Modes

Let m = len(s) and n = len(t).

Building need takes O(n) time. The right pointer advances exactly m times. The left pointer also advances at most m times overall; it never moves backward. Each pointer movement performs constant expected-time map operations.

Therefore:

Time:  O(m + n)
Space: O(k)

Here, k is the number of distinct characters tracked in the maps. Under the stated alphabet, k is bounded by the alphabet size. The map formulation is still best understood as O(k) auxiliary state rather than as a mysterious constant.

Test the transitions, not just the happy path:

Case	Expected behavior
s = "a", t = "a"	Return "a"
s = "a", t = "aa"	Return ""; multiplicity cannot be met
s = "abc", t = "z"	Return ""; no required character appears
s = "xxa...b...cxx", t = "abc"	Ignore irrelevant characters for validity but remove them during shrinking
s = "AAAB", t = "AAB"	Keep surplus As removable without breaking validity
s = "ab", t = "b"	The answer can be a one-character window at the end
s = "aA", t = "A"	Match uppercase A, not lowercase a

The most dangerous implementation errors are state-transition errors:

Using len(t) for required

If t = "AAB", len(t) == 3, but there are only two distinct requirements. With a formed counter that counts distinct thresholds, the correct value is:

required = len(need)  # 2

An alternative design can count matched characters and compare against len(t), but that is a different invariant. Do not mix the two models.

Incrementing formed for every required character

If need['A'] == 2, adding the first A does not complete the A requirement. Increment only when the count reaches exactly 2.

Decrementing formed whenever a required character is removed

Removing a surplus copy should not make a valid window invalid. Decrement only when the count falls below the target.

For example, with need['A'] == 2, a window containing three As can lose one A and remain valid.

Shrinking before recording

The current window is the valid candidate. Save it first. Then test whether the contraction remains valid.

Treating case as interchangeable

The contract is case-sensitive. A map naturally preserves that distinction; avoid normalizing characters unless the problem explicitly asks for it.

Carry the Pattern Forward

The reusable rule is precise:

When a contiguous interval must satisfy per-item lower bounds, and removing prefix material can improve the objective, expand until valid and shrink until invalid.

The pattern is not “use two pointers whenever a string appears.” The decision depends on a monotonic boundary:

• Adding items to the right cannot make a lower-bound coverage condition worse.
• Removing items from the left cannot make that condition better.
• Once a left removal breaks validity for a fixed right boundary, further left removals will not repair it.

Before writing pointer code, name the invariant in one sentence:

Which requirements are satisfied, and what exact count transition changes one requirement from unsatisfied to satisfied—or back again?

That question separates a real sliding-window derivation from a memorized template.

One useful reimplementation exercise is to track matched characters instead of formed:

• increment when adding a required copy that is still needed;
• decrement when removing a copy that was contributing to the target;
• declare validity when the matched count equals len(t).

That version is correct, but its invariant is different. Comparing the two implementations forces you to distinguish:

• distinct satisfied requirements;
• total matched target copies.

That distinction transfers directly to other frequency-constrained windows.

The broader boundary also matters. This technique depends on validity changing predictably as the left boundary moves. If removing an element can make a non-monotone condition become valid again, “shrink until invalid” is no longer automatically safe. Name the condition first. Then choose the window mechanics. Clear the noise, track the thresholds, and keep the last valid interval before the failure.