Typorithm · hard

Minimum Window Substring

minimum-window-substringsliding-windowvariable-windowneed-mapcontract

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Minimum Window Substring

Sliding Window

Expand right until the window covers all of t, then contract from the left while still valid, tracking the smallest.

Find the shortest substring of s containing every character of t with the right multiplicities.

Expand right until required reaches 0, meaning all needed characters are covered.

Then contract from the left as far as the window stays valid, recording the minimum width each time.

Expand right to satisfy all needs.

Contract left while still valid.

Record the smallest valid window.

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

  const need = new Map();
  for (const ch of t) {
    need.set(ch, (need.get(ch) ?? 0) + 1);
  }

  let required = need.size;
  let left = 0;
  let bestLen = Infinity;
  let bestStart = 0;

  for (let right = 0; right < s.length; right += 1) {
    const rc = s[right];
    if (need.has(rc)) {
      need.set(rc, need.get(rc) - 1);
      if (need.get(rc) === 0) {
        required -= 1;
      }
    }

    while (required === 0) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestStart = left;
      }
      const lc = s[left];
      if (need.has(lc)) {
        if (need.get(lc) === 0) {
          required += 1;
        }
        need.set(lc, need.get(lc) + 1);
      }
      left += 1;
    }
  }

  return bestLen === Infinity ? "" : s.substring(bestStart, bestStart + bestLen);
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Required counts

Count each character the target t requires.

need.set(ch, (need.get(ch) ?? 0) + 1)

2. Char satisfied

A count reaching 0 means that character is fully covered.

if (need.get(rc) === 0) {
        required -= 1;
      }

3. Shrink while valid

Once all needs are met, shrink from the left to minimize.

while (required === 0) {

4. Record smallest

Keep the shortest valid window seen.

if (right - left + 1 < bestLen) {

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.