Minimum Window Substring

The problem

Given two strings s and t, return the shortest substring of s, a run of neighboring characters, that contains every character of t. A character that appears more than once in t must appear at least that many times in the substring. The characters can be in any order, and the substring may hold other characters too. If no substring qualifies, or t is empty, return an empty string. When a substring qualifies, the shortest one is unique.

What to write

function solve(s: string, t: string): string

Input
s = "ADOBECODEBANC"
t = "ABC"

Output
"BANC"

Input
s = "a"
t = "aa"

Output
""

Constraints

When a window exists its minimum is unique; s and t have at most 100000 characters.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Each string can hold 100,000 characters, and s then has about 5 billion substrings, far too many to look at even once. Aim to pass over s a fixed number of times. Repeats in t count too: if t is "aa", a single a is not enough.

2. Hint 2: Ask a smaller question

   The stretch "DOBECODEBA" contains an A, a B and a C. Which characters can you remove from its left end, one at a time, so that it still does? What stops you, and why did the first B not stop you?

3. Hint 3: Name the pattern

   You want the shortest stretch that meets a condition. A character taken in on the right can only help, and one given up on the left can only hurt. So grow a window to the right until it holds all of t, then shrink it from the left while it still does. This is a variable sliding window. Read the lesson on variable sliding window.

4. Hint 4: State the invariant

   For each character, keep how many more copies the window needs. A negative number means spare copies. Keep one total as well: how many characters of t are still missing. The window holds all of t exactly when that total is 0.

5. Hint 5: Sketch the pseudocode

   Empty t: return "". Count t into need; missing = t's length. For each c in s: if c's need is above 0, lower missing; then lower c's need. While missing is 0: keep the window if shortest; raise the leftmost character's need, and missing if that need is above 0; move the left edge up. Return the kept window.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Count missing character occurrences, extend until valid, then shrink while preserving coverage.

The slow way

Check every substring of s: count its characters, see whether it has everything t needs, and keep the shortest that does. It is correct, but 100,000 characters make about 5 billion substrings, and each one is counted from scratch.

The insight

Take a window, a stretch of s between a left and a right edge. Once the window holds all of t, making it longer on the right cannot make it better. So shrink it from the left instead, until a character it needs is lost. One number says whether the window is complete: how many characters of t are still missing.

Step by step

1. An empty t asks for nothing, so return an empty string. With nothing to find, nothing is ever missing, so the shrinking loop below has no reason to stop and runs past the right edge. Answering here avoids that.
2. Count how many of each character the window still needs. These counts start as the counts of t and change as characters enter and leave the window. A count above zero means the window is still waiting for that character.
3. Start with an empty window: all of t is missing, no window is kept. The window starts empty at the left end of s, so the number of missing characters is the length of t. The shortest length starts at infinity, which stands for no window found yet.
4. Take the next character: if it was still needed, one fewer is missing. The character's count goes down either way. So the count drops below zero for spare copies and for characters t does not contain, and such characters never change the number missing.
5. While nothing is missing, the window covers t: keep it if shortest. The window is measured before it shrinks, while it is known to hold everything. Only a shorter window replaces the one already kept, and its start and length are enough to cut it out of s later.
6. Give the leftmost character back and move the left edge past it. Giving a character back raises its count. If the count is now above zero, the window had no spare copy, so that character is missing again and the shrinking stops.
7. Return the shortest window found, or an empty string if there is none. If the window never held all of t, the shortest length is still infinity, and the answer is the empty string.

The same numbered steps are the comments in each solution.

function solve(s, t) {
  // 1. An empty t asks for nothing, so return an empty string
  if (!t) return "";
  // 2. Count how many of each character the window still needs
  const need = new Map();
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
  // 3. Start with an empty window: all of t is missing, no window is kept
  let missing = t.length,
    l = 0,
    start = 0,
    size = Infinity;
  for (let r = 0; r < s.length; r++) {
    // 4. Take the next character: if it was still needed, one fewer is missing
    if ((need.get(s[r]) || 0) > 0) missing--;
    need.set(s[r], (need.get(s[r]) || 0) - 1);
    // 5. While nothing is missing, the window covers t: keep it if shortest
    while (missing === 0) {
      if (r - l + 1 < size) {
        size = r - l + 1;
        start = l;
      }
      // 6. Give the leftmost character back and move the left edge past it
      need.set(s[l], (need.get(s[l]) || 0) + 1);
      if (need.get(s[l]) > 0) missing++;
      l++;
    }
  }
  // 7. Return the shortest window found, or an empty string if there is none
  return size === Infinity ? "" : s.slice(start, start + size);
}

function solve(s: string, t: string): string {
  // 1. An empty t asks for nothing, so return an empty string
  if (!t) return "";
  // 2. Count how many of each character the window still needs
  const need = new Map<string, number>();
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
  // 3. Start with an empty window: all of t is missing, no window is kept
  let missing = t.length,
    l = 0,
    start = 0,
    size = Infinity;
  for (let r = 0; r < s.length; r++) {
    // 4. Take the next character: if it was still needed, one fewer is missing
    if ((need.get(s[r]) || 0) > 0) missing--;
    need.set(s[r], (need.get(s[r]) || 0) - 1);
    // 5. While nothing is missing, the window covers t: keep it if shortest
    while (missing === 0) {
      if (r - l + 1 < size) {
        size = r - l + 1;
        start = l;
      }
      // 6. Give the leftmost character back and move the left edge past it
      need.set(s[l], (need.get(s[l]) || 0) + 1);
      if (need.get(s[l])! > 0) missing++;
      l++;
    }
  }
  // 7. Return the shortest window found, or an empty string if there is none
  return size === Infinity ? "" : s.slice(start, start + size);
}

def solve(s, t):
    # 1. An empty t asks for nothing, so return an empty string
    if not t:
        return ""
    # 2. Count how many of each character the window still needs
    need = {}
    for char in t:
        need[char] = need.get(char, 0) + 1
    # 3. Start with an empty window: all of t is missing, no window is kept
    missing = len(t)
    left = start = 0
    size = float("inf")
    for right, char in enumerate(s):
        # 4. Take the next character: if it was still needed, one fewer is missing
        if need.get(char, 0) > 0:
            missing -= 1
        need[char] = need.get(char, 0) - 1
        # 5. While nothing is missing, the window covers t: keep it if shortest
        while missing == 0:
            if right - left + 1 < size:
                size = right - left + 1
                start = left
            # 6. Give the leftmost character back and move the left edge past it
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    # 7. Return the shortest window found, or an empty string if there is none
    return "" if size == float("inf") else s[start : start + size]

Example 1, traced

Input
s = "ADOBECODEBANC"
t = "ABC"

Output
"BANC"

Why it works

Wherever the left edge stands, the right edge stops at the first place, if any, where the window holds all of t. That is the shortest window starting there, and it is measured before the left edge moves on. The shortest window of all starts somewhere, so it is among them. Counts below zero remember spare copies, so a character is missing only when the window has too few.

Time and space

Time O(n + m), extra space O(alphabet). Counting t takes m steps. The right edge passes over each of the n characters of s once, and the left edge only moves forward, at most n times: O(n + m). The table holds one count per different character, which is at most the size of the alphabet.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Count how many copies of each character t holds. A set of its characters loses the repeats. With s = "a" and t = "aa" the answer comes out as "a", but one a is not enough.
• Shrink with a loop, not with a single test. One step from the left is rarely enough: with a single step, example 1 returns "ADOBEC" and never gets down to "BANC".
• Let a count drop below zero for spare copies. If you stop at zero, the first B to leave "DOBECODEBA" looks like a loss although a second B is still inside, and example 1 returns "ADOBEC".

Pattern

Variable sliding window. Builds on Longest Repeating Character Replacement and Permutation In String.

Keep going