Coding Interview: How Do You Solve Minimum Window Substring?

Problem and When It Applies

Given strings s and t, find the shortest contiguous substring of s that contains every character from t at least as many times as it occurs in t. Matching is case-sensitive. For example:

s = "ADOBECODEBANC"
t = "ABC"
output = "BANC"

If t = "AABC", a candidate window needs at least two A characters, one B, and one C. A set-membership check loses this multiplicity requirement, which is the most common semantic mistake in this problem.

The constraints are 1 <= s.length, t.length <= 100000, and both strings contain only uppercase and lowercase English letters. If an answer exists, the shortest answer is unique. Return an empty string when no window covers t. The implementation below also handles an empty t and s shorter than t defensively, although those inputs are outside the standard constraints.

Recent public software engineering interview records still show Minimum Window Substring, including a variation where t has no duplicate characters. Both English and Chinese coding platforms also retain the problem. Its core skill is turning a global minimum-interval search into incrementally maintained state, so the accurate category is coding; the example language does not change that classification.

What the Interviewer Is Evaluating

The first signal is precise modeling. A strong answer expresses “contains t” as a frequency constraint: for every target character c, the current window must satisfy window[c] >= need[c]. Merely saying that all target characters have appeared cannot handle t = "AA".

The second signal is recognizing monotonicity behind the quadratic baseline. Moving the right boundary only adds characters, so a valid window stays valid when expanded. For a fixed right boundary, moving the left boundary removes characters. Once the window is valid, it can be contracted until it has just become invalid, recording shorter candidates along the way.

The third signal is compressing the validity check. Scanning the entire frequency table on every move loses the linear bound. The implementation uses formed for the number of target character classes whose required frequency has been reached, with required = need.size. formed increases when a frequency first becomes equal to its requirement and decreases when removal takes it below that requirement. Surplus copies do not count twice.

Finally, the candidate should justify correctness and boundaries: why the shortest valid window for every right boundary is examined, why discarded left endpoints cannot produce a better future candidate, and why each pointer moves at most s.length times.

Questions to Clarify Before Answering

• Is matching case-sensitive? It is here. If matching should ignore case, define normalization first; normalization can change

the mapping back to indices in the original string.

• Does “contains” preserve the order from t? No. This problem only requires frequency coverage. Requiring order produces the

Minimum Window Subsequence problem, for which this validity condition does not work.

• Do duplicate target characters count separately? Yes. t = "AABC" requires two A characters, directly motivating a

frequency map.

• What happens when several shortest windows tie? The standard problem guarantees uniqueness. Without that guarantee, this

implementation returns the earliest shortest window because it only updates on a strictly smaller length.

• What is the character set? Inputs are English letters, so indexing JavaScript UTF-16 code units cannot split an allowed

character. For arbitrary Unicode, first define whether matching operates on code points or user-perceived grapheme clusters.

• Can either string be empty? The standard constraints exclude empties. The sample function returns an empty string for empty

t, empty s, or s.length < t.length.

• Should the function return text or indices? The main problem returns text. For indices, return

[bestStart, bestStart + bestLength) without changing the core scan.

These questions can change the validity predicate, index representation, or output rule. Language preference, variable names, and the specific hash-map implementation do not change the algorithm choice.

30-Second Answer Framework

“I’ll count target frequencies in need and maintain a window with two pointers. As the right pointer expands, formed increases only when one character class first reaches its requirement. Once every class is satisfied, I record the answer and advance the left pointer until the window becomes invalid. That examines the shortest valid window for each right endpoint. Both pointers move only right, so every position enters and leaves at most once: O(|s| + |t|) time and O(u) frequency-map space.”

Step-by-Step Deep Dive

Step 1: Use the baseline to expose repeated work.

For each left endpoint, one can extend a right endpoint while maintaining frequencies and stop at the first valid window. This avoids recounting every substring, but it may still rescan most of s from every left endpoint, taking O(|s|^2 + |t|) time. Recounting every substring from scratch can be cubic.

Here, u is the number of distinct characters in t, at most 52 under the English-letter constraint. The state design remains the important part of the linear solution; a small alphabet should not hide an incorrect validity check.

Step 2: Define enough state for a constant-time validity check.

need stores target frequencies. window stores frequencies of target characters in the current window. required = need.size is the number of character classes to satisfy, and formed is the number that have reached their required frequency. The window is valid exactly when formed === required.

Updates must be tied to crossing a requirement threshold:

after adding c: window[c] changes from need[c]-1 to need[c], so formed += 1
after adding c: window[c] changes from need[c] to need[c]+1, so formed is unchanged
before removing c: window[c] equals need[c], so removal causes formed -= 1
before removing c: window[c] exceeds need[c], so removal leaves formed unchanged

Treating formed as a raw count of target characters makes surplus copies easy to overcount. Incrementing on every target character without capping the contribution would incorrectly mark t = "AABC" as covered too early.

Step 3: Fix the order of expansion, recording, and contraction.

The right pointer includes s[right] and updates state. When the window becomes valid, the inner loop first considers [left, right] for the answer and then prepares to remove s[left]. If removal makes one character class deficient, decrement formed, reduce the frequency, and advance left.

Recording before removal prevents a valid candidate from being skipped. Testing equality before decrementing the frequency makes the threshold transition explicit. A correct implementation can decrement first and test for a value below the requirement, but the explanation and condition must use the same ordering.

Step 4: Implement the linear scan.

export function minWindow(s: string, t: string): string {
  if (t.length === 0 || s.length < t.length) return "";

  const need = new Map<string, number>();
  for (const char of t) {
    need.set(char, (need.get(char) ?? 0) + 1);
  }

  const window = new Map<string, number>();
  const required = need.size;
  let formed = 0;
  let left = 0;
  let bestStart = 0;
  let bestLength = Number.POSITIVE_INFINITY;

  for (let right = 0; right < s.length; right += 1) {
    const char = s[right];
    const target = need.get(char);

    if (target !== undefined) {
      const nextCount = (window.get(char) ?? 0) + 1;
      window.set(char, nextCount);
      if (nextCount === target) formed += 1;
    }

    while (formed === required) {
      const length = right - left + 1;
      if (length < bestLength) {
        bestStart = left;
        bestLength = length;
      }

      const leftChar = s[left];
      const leftTarget = need.get(leftChar);
      if (leftTarget !== undefined) {
        const currentCount = window.get(leftChar) ?? 0;
        if (currentCount === leftTarget) formed -= 1;
        window.set(leftChar, currentCount - 1);
      }
      left += 1;
    }
  }

  return Number.isFinite(bestLength)
    ? s.slice(bestStart, bestStart + bestLength)
    : "";
}

The implementation stores counts only for target characters. Non-target characters still affect the window length and its left boundary, so they cannot be deleted from s in advance; they simply do not need entries in the frequency map.

Step 5: State the invariants and prove correctness.

At the end of each outer-loop iteration, the following facts hold:

1. window[c] equals the actual count of target character c in the current interval [left, right].
2. formed equals exactly the number of target classes satisfying window[c] >= need[c].
3. After the inner loop ends, the current window is invalid. The last valid window just examined was the shortest valid window for

that right endpoint.

1. left moves only rightward. Any earlier left endpoint already passed would create a longer window for the same right endpoint,

and extending the right endpoint later cannot make it beat a candidate already considered at that earlier endpoint.

The empty initial window satisfies the first two invariants. Adding the right character updates its actual count, and the threshold rule preserves the second invariant. While the window is valid, the algorithm records the candidate before every removal, so it examines all valid left boundaries ending at the current right until the first two invariants say the window is invalid. By induction over right endpoints, the algorithm examines the shortest valid window for each one. The global optimum must be among those candidates, so the recorded answer is correct.

Step 6: Trace a target with duplicate characters.

Let s = "AAABBC" and t = "AABC":

need = {A:2, B:1, C:1}, required = 3
right=0, A:1  formed=0
right=1, A:2  formed=1
right=2, A:3  formed=1    surplus A does not count twice
right=3, B:1  formed=2
right=4, B:2  formed=2    surplus B does not count twice
right=5, C:1  formed=3    [0,5] is valid
remove A at index 0: A:2, still valid; record [1,5] = "AABBC"
remove another A: A:1, formed falls to 2, so contraction stops

This trace checks three independent details: a required frequency above one, no double-counting above the requirement, and continued contraction after removing a surplus copy.

Step 7: Analyze complexity accurately.

Building need scans t once. The right pointer scans s once, and the left pointer can move from 0 to s.length only once over the entire execution. The cumulative work of the inner while loop is therefore O(|s|). With average O(1) map operations, total time is O(|s| + |t|). The two frequency maps store at most u target characters, so extra space is O(u); under the English-letter constraint, u <= 52.

Step 8: Verify with an oracle and properties.

At minimum, fixed tests should cover:

("ADOBECODEBANC", "ABC") -> "BANC"   standard mixed input
("AAABBC", "AABC")       -> "AABBC"  duplicate requirement
("a", "a")               -> "a"      minimum size
("a", "A")               -> ""       case-sensitive and impossible
("abc", "abcd")          -> ""       s is shorter than t
("abc", "")              -> ""       defensive empty target

For short random strings, compare against a quadratic oracle that enumerates every interval. Check three properties of the optimized result: it is a contiguous substring of s, its frequencies cover t, and no shorter interval covers t. Differential testing is especially effective at exposing an overcounted formed, off-by-one answer lengths, and incorrect removal order.

When s is tiny, the operation is one-off, and performance is unconstrained, the quadratic version is shorter and may be safer to write under interview pressure. With a length bound of 100000 and an explicit linear-time target, the sliding window is the appropriate final solution.

High-Quality Sample Answer

“I would first confirm that containment is based on character frequencies, order does not matter, and matching is case-sensitive. A baseline fixes each left endpoint and expands right, which is quadratic in the worst case. This problem has useful monotonicity: adding a right character cannot invalidate a valid window, and once a window is valid, advancing the left endpoint can find the shortest valid window ending at that right endpoint.

I will store t frequencies in need and current target frequencies in window. I will also maintain formed, the number of character classes that have reached their requirement. Adding a character increments formed only when its count becomes exactly the required count. While the window is valid, I record it before removing the left character. If that character is exactly at its required count before removal, the removal makes the class deficient, so I decrement formed.

The key invariants are that window matches the true counts in [left, right] and that formed matches the number of satisfied target classes. The inner loop checks every valid left boundary for each right endpoint and stops just after passing the shortest valid one. The global optimum is among those candidates. Both pointers move only to the right, so every position enters and leaves at most once. The time is O(|s| + |t|) and space is O(u). I would test a duplicate target, no solution, one-character inputs, case differences, and random short strings against a brute-force oracle.”

Common Mistakes

• Store only a set of target characters → duplicate requirements disappear → store required frequencies.
• Increment the match count for every target character added → surplus copies create false validity → **increment formed

only on the first transition to the required count.**

• Always decrement formed when removing a target character → removing a surplus copy leaves the window valid → **decrement

only when the pre-removal count equals the requirement.**

• Contract only once after becoming valid → shorter windows ending at the same right boundary are skipped → **use a while

loop until the window first becomes invalid.**

• Move left before recording the answer → a valid minimum can be skipped or measured off by one → **measure

[left, right] first.**

• Scan all of need after every pointer move → validity checking adds a factor of u → **maintain the satisfied-class count

incrementally.**

• Solve a subsequence problem → positions inside the result may be skipped, so the answer is no longer contiguous → **represent

every window as one continuous index interval.**

• Filter non-target characters and then slice the original string with filtered indices → filtered positions do not map

directly back to the source → keep pointers on the original string and ignore non-targets only in the maps.

• Call the inner loop quadratic → this ignores the globally monotone left pointer → **amortize over each position leaving at

most once.**

• Test only the standard example → duplicates, impossible cases, and case sensitivity remain untested → **add fixed adversarial

cases and a random oracle.**

Follow-Up Questions and Responses

Follow-up 1: Why count satisfied character classes instead of total matched characters?

Either state can support a correct algorithm, but class counting makes threshold transitions explicit. For need[A] = 2, the class becomes satisfied only when window[A] moves from 1 to 2; a third A does not change that status. Removal cancels the status only when the count moves from 2 to 1. A total-character counter must increment only while window[c] <= need[c] and use a symmetric removal rule, which is easier to misstate.

Follow-up 2: What can be simplified if t has no duplicate characters?

Every value in need is 1, so window can be represented by target-character counts or by a set paired with occurrence counts. Repeated copies of the same target can still appear in the window, and removing one copy may leave the class satisfied. Keeping the general frequency implementation adds little constant overhead and directly handles the original problem.

Follow-up 3: What if characters must appear in the order specified by t?

That is Minimum Window Subsequence. Frequency coverage no longer proves validity: s = "cba" covers the frequencies of t = "abc" but has the wrong order. A solution can use dynamic programming to retain the start position for each matched prefix, or forward and backward scans around candidate endpoints. Its complexity needs a new analysis, and formed === required cannot be reused as the validity condition.

Follow-up 4: How would you return every tied shortest window?

Without the uniqueness guarantee, keep bestLength as before. When a shorter window appears, clear the result list and add that interval. When an equal-length window appears, append it. If separate search paths could rediscover the same text interval, dedupe by [left, right]; this two-pointer traversal visits each interval at most once, so no extra set is needed here.

Follow-up 5: What if s is a character stream that cannot fit in memory?

The required frequencies and pointer state can still be updated online, but returning the original text requires retaining the current candidate interval. A queue can store characters from left through the newest position with global offsets. If no valid window appears for a long time, that buffer can approach the entire stream read so far. Returning only a length and offsets allows more compression around target-character positions; returning text requires an explicit maximum-window or external-storage policy.

Follow-up 6: How would you support arbitrary Unicode text?

First define the unit of matching. For Unicode code points, iterate by code point and retain the corresponding UTF-16 code-unit offsets for slicing the original JavaScript string. A user-perceived character may contain several code points; matching grapheme clusters requires a reliable segmenter. Normalization also changes the definition of character equality, so it must be applied consistently before counting while preserving a mapping to the source text.

Follow-up 7: How can you trust the randomized test oracle?

The oracle runs only on short strings, so it can enumerate every [left, right], recount each interval directly, and choose by length and start position. Its control flow is deliberately different from the optimized algorithm, making it slow but easy to audit. Validate the oracle on fixed examples first, then compare result length, contiguity, and frequency coverage during random differential tests to reduce the chance of a shared bug.