Minimum Window Substring Explained: Tracing ADOBECODEBANC for ABC

Imagine you are handed a massive string $s=\text{"ADOBECODEBANC"}$ and a tiny target string $t=\text{"ABC"}$. Your mission is to find the absolute smallest contiguous slice of $s$ that contains every single character in $t$, including duplicates. For our locked working example, the expected result is $\text{"BANC"}$, which spans 4 characters. While $\text{"ADOBEC"}$ also contains all three characters, it is length 6 and therefore too long.

If you approach this with brute force, you might generate every possible substring of $s$, check each one to see if it holds an $\text{"A"}$, a $\text{"B"}$, and a $\text{"C"}$, and then pick the shortest. But a string of length 14 has 105 non-empty substrings, and that number scales quadratically as $O(N^2)$. Scale $s$ up to one million characters, and the brute-force approach stalls out entirely.

To avoid this quadratic trap, we need a mechanism that inspects each character at most a constant number of times. Instead of starting over for every candidate substring, we want to slide a dynamic boundary across $s$, expanding when we lack characters and contracting when we have a valid covering window.

s = "ADOBECODEBANC"
t = "ABC"
# Goal: Find the shortest substring of s containing 'A', 'B', and 'C'
# Expected answer: "BANC" (length 4)

To capture the smallest substring of $s=\text{"ADOBECODEBANC"}$ containing every character of $t=\text{"ABC"}$, we cannot afford to re-scan every possible window from scratch. Instead, we maintain two pointers, left and right, starting together at index 0. The right pointer explores outward, greedily taking in characters to satisfy our character requirements, while the left pointer trails behind, trying to squeeze the window as tight as possible without losing validity.

Imagine our algorithm as a physical band stretching across a timeline. As the right pointer moves from index 0 to 5, our window becomes $\text{"ADOBEC"}$. This span includes 'A', 'B', and 'C', satisfying our frequency requirements for $t$. But is it the minimum? At this moment, the left pointer steps in, incrementing forward to see if we can drop the leading 'A' or 'D'. The core mechanism relies on a frequency map that counts how many of each target character we still need to enclose before the window is considered complete.

As right expands, we decrement our shortage count for matching characters. When shortage reaches zero, the window is complete. Then, left contracts until shortage ticks back up, recording the window length at each valid shrinkage step.

Try this: Given s = "ADOBECODEBANC" and t = "ABC", explain in your own words what condition triggers the left pointer to contract, and what condition triggers the right pointer to expand.

To see the two-pointer sliding window in action, let us trace our locked example: finding the minimum window in $s=\text{"ADOBECODEBANC"}$ that covers $t=\text{"ABC"}$.

We start with a target frequency map for $t$: {'A': 1, 'B': 1, 'C': 1}, meaning we need 3 unique character fulfillments, and a missing count of 3. Both pointers, left and right, begin at index 0.

- String $s=\text{"ADOBECODEBANC"}$ (length 13)
- Target $t=\text{"ABC"}$
- Required counts: $\text{A}=1,\text{B}=1,\text{C}=1$

1. Expand Right: We advance right from 0 to 5, spelling out ADOBEC.
- When right hits index 5 (character 'C'), all characters of $t$ are satisfied.
- Our missing count drops to 0.
- Current window: ADOBEC (length 6, indices 0 to 5).

2. Shrink Left: Now we try to optimize by advancing left while keeping the window valid ($\text{missing}==0$).
- Advance left from 0 to 1 (dropping 'A'). Wait, 'A' is required! But our window frequency map still allows it if we haven't broken the threshold. Actually, tracking carefully: dropping index 0 ('A') makes 'A' count go to 0, which violates our requirement since we need 1 'A'.
- So when left is at 0, dropping 'A' increments missing back to 1. We stop shrinking. The best window found so far is ADOBECODEBANC[0..5] = ADOBEC of length 6.

- We resume expanding right past index 5. We sweep through ODEB until we hit index 10 ('A'), then index 11 ('N'), and finally index 12 ('C').
- When right hits index 12 (the final 'C'), the window spans from left index 9 to right index 12, which is BANC.
- Let's inspect the window BANC (indices 9 to 12): it contains 'B', 'A', 'N', 'C'. This includes all characters of $t$.
- We now shrink left from index 9. If we move left past 'B' (index 9), we lose 'B', so $\text{missing}$ becomes 1 again. Thus, the window cannot shrink further from the left.
- During this sweep, we also encountered windows like CODEBANC and tested shrinking them. The shortest valid window recorded during the entire run is length 4.

The algorithm successfully identifies the minimum window substring as $\text{"BANC"}$ with a length of 4, beating our initial candidate $\text{"ADOBEC"}$ (length 6).

Try this: Trace the algorithm for s = "ADOBECODEBANC" and t = "ABC". At what index of right does the window first become valid, and what characters are inside that initial window?

Now that you have traced how the window expands right and contracts left on the classic $s=\text{"ADOBECODEBANC"}$ and $t=\text{"ABC"}$ example, it is time to test your mental model against a slight variation. Suppose we change the target string $t$ to $\text{"AAB"}$ while keeping the same source string $s=\text{"ADOBECODEBANC"}$.

Recall that the frequency map for $\text{"AAB"}$ requires at least two $\text{’A’}$ characters and one $\text{’B’}$. As your right pointer expands across the source string, you must accumulate these frequencies before your window becomes valid and the left pointer begins its contraction phase. Think carefully about how the frequency map state machine responds to duplicate characters in $t$ and when the first valid window can finally shrink.

Given the source string $s=\text{"ADOBECODEBANC"}$ and the modified target $t=\text{"AAB"}$, trace the right pointer's expansion until the window first satisfies all frequency requirements. At that exact moment of first validity, what is the exact substring enclosed between your left and right pointers, and how many times can you immediately increment the left pointer before the window becomes invalid again?

s = "ADOBECODEBANC"
t = "AAB"
# Exercise: Determine the exact window bounds when validity is first reached,
# and trace how far the left pointer can shrink while maintaining validity.

We have successfully tracked our minimum window across the string $s=\text{"ADOBECODEBANC"}$ for target $t=\text{"ABC"}$, arriving at the optimal result $\text{"BANC"}$. The power of this two-pointer expansion-contraction strategy is that it generalizes far beyond literal text manipulation. Whenever you face a collection of items where a contiguous subarray or segment must satisfy a set of inclusion criteria, the identical frequency-mapping and validity-counter mechanics apply.

Consider a neighboring problem: finding the smallest subarray of integers in an array $A$ that contains a specific set of required target values, or finding the shortest sub-segment of network log entries that contains a complete set of required error codes. The state variables change from character frequencies to integer counts or hash map bucket sizes, but the algorithm skeleton remains isomorphic.

To test this transfer of knowledge, apply the sliding window framework to the question below without resetting your mental model of the expand-right, shrink-left invariant.