Minimum Window Substring: Step-by-Step Solution

Some coding interview problems look simple until you try to make them fast. Minimum Window Substring is one of those classics: given two strings, find the smallest substring in the first string that contains every character from the second string. The trick is not merely checking substrings, but learning how to expand and shrink a window efficiently until the answer reveals itself.

Understanding the Problem

The problem usually looks like this:

Given two strings s and t, return the minimum window substring of s such that every character in t is included in the window. If no such window exists, return an empty string.

For example:

s = "ADOBECODEBANC"
t = "ABC"
answer = "BANC"

The substring "BANC" contains A, B, and C, and no shorter substring in s satisfies the requirement.

A key detail is that character counts matter. If t = "AABC", then a valid window must contain two A characters, one B, and one C. Simply checking whether a character appears is not enough.

Why the Brute Force Approach Fails

The most direct solution is to examine every possible substring of s and check whether it contains all characters from t. This works conceptually, but it is slow.

• There are about n² possible substrings.
• Checking each substring may require counting characters.
• The total runtime can become O(n³) or O(n²) with optimization.

For small inputs, brute force is acceptable. For real interview constraints, it is usually too slow. We need a method that avoids repeatedly rechecking the same characters.

The Sliding Window Idea

The sliding window technique is ideal when you need to find a contiguous segment of a string or array that satisfies certain conditions. Instead of generating every substring, we maintain a moving range between two indexes:

• left: the start of the current window
• right: the end of the current window

We expand the window by moving right. Once the window contains all required characters, we try to shrink it by moving left. This push-and-pull process lets us explore useful windows without wasting time on clearly invalid ones.

Step 1: Count the Required Characters

First, build a frequency map for t. This map tells us exactly what the window must contain.

t = "ABC"

need = {
  A: 1,
  B: 1,
  C: 1
}

If t = "AABC", then:

need = {
  A: 2,
  B: 1,
  C: 1
}

We also track how many unique character requirements must be satisfied. In the first example, that number is 3: one requirement for A, one for B, and one for C.

Step 2: Expand the Window

Now move the right pointer across s. Each time a character enters the window, update another frequency map called window.

If the newly added character is one we care about, and its count in window equals its required count in need, we have satisfied one requirement.

For s = "ADOBECODEBANC" and t = "ABC", the window becomes valid for the first time when it reaches "ADOBEC". At that point, it contains A, B, and C.

Step 3: Shrink the Window

Once all requirements are satisfied, the window is valid. But it may not be minimal. This is where the algorithm becomes clever: we move left forward while the window remains valid.

Each time before shrinking, we check whether the current window is the smallest valid one seen so far. If it is smaller, we store its length and indexes.

Then we remove the character at left from the window count. If removing it causes the window to no longer meet a required count, the window becomes invalid, and we stop shrinking. After that, we continue expanding with right.

Step-by-Step Walkthrough

Let’s walk through the famous example:

s = "ADOBECODEBANC"
t = "ABC"

1. Start with left = 0 and move right forward.
2. When the window reaches "ADOBEC", it contains all required characters.
3. Record "ADOBEC" as the current best answer.
4. Move left forward. Removing A breaks the requirement, so stop shrinking.
5. Continue expanding until another valid window appears.
6. Eventually, the window "CODEBANC" becomes valid.
7. Shrink from the left: remove unnecessary characters until the window becomes "BANC".
8. "BANC" is valid and shorter than the previous best, so update the answer.

The final result is:

"BANC"

Reference Implementation

Here is a clean JavaScript version of the sliding window solution:

function minWindow(s, t) {
  if (t.length > s.length) return "";

  const need = {};
  const window = {};

  for (const char of t) {
    need[char] = (need[char] || 0) + 1;
  }

  const required = Object.keys(need).length;
  let formed = 0;

  let left = 0;
  let bestLength = Infinity;
  let bestStart = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    window[char] = (window[char] || 0) + 1;

    if (need[char] && window[char] === need[char]) {
      formed++;
    }

    while (formed === required) {
      const currentLength = right - left + 1;

      if (currentLength < bestLength) {
        bestLength = currentLength;
        bestStart = left;
      }

      const leftChar = s[left];
      window[leftChar]--;

      if (need[leftChar] && window[leftChar] < need[leftChar]) {
        formed--;
      }

      left++;
    }
  }

  return bestLength === Infinity
    ? ""
    : s.slice(bestStart, bestStart + bestLength);
}

Why This Works

The algorithm works because every character is processed at most twice: once when right includes it, and once when left removes it. We never restart from scratch, and we never check every substring separately.

The variable formed is especially important. It tells us how many unique character requirements are currently satisfied. When formed === required, the window is valid. This is more efficient than comparing entire maps every time the window changes.

Complexity Analysis

• Time complexity: O(n + m), where n is the length of s and m is the length of t.
• Space complexity: O(k), where k is the number of distinct characters stored in the maps.

In many practical cases, if the character set is limited, the space usage can be considered constant.

Common Mistakes to Avoid

• Ignoring duplicate characters: Remember, "AABC" requires two A characters.
• Shrinking too early: Only shrink when the window is already valid.
• Comparing full maps repeatedly: Use a counter like formed instead.
• Forgetting to update the best window before removing characters: The current valid window may be the answer.

Final Thoughts

Minimum Window Substring is a perfect example of how a simple idea can become powerful with the right structure. The sliding window approach turns a potentially expensive search into a smooth linear scan. Once you understand the rhythm of expand until valid, shrink until invalid, the problem becomes much less mysterious.

This pattern also appears in many other string and array problems, so mastering it pays off well beyond this single challenge. Think of the window as a spotlight moving across the string: it grows to find what it needs, then tightens to focus on the smallest possible answer.