Minimum Window Substring

hard string sliding window hash map

Problem

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Inputs = "ADOBECODEBANC", t = "ABC"

Output"BANC"

Window "BANC" at indices 9..12 contains A, B, and C — and no shorter window does.

from collections import Counter

def min_window(s, t):
    need = Counter(t)
    required = len(need)
    have = Counter()
    formed = 0
    l = 0
    best = (float("inf"), 0, 0)
    for r, c in enumerate(s):
        have[c] += 1
        if c in need and have[c] == need[c]:
            formed += 1
        while formed == required:
            if r - l + 1 < best[0]:
                best = (r - l + 1, l, r)
            lc = s[l]
            have[lc] -= 1
            if lc in need and have[lc] < need[lc]:
                formed -= 1
            l += 1
    return "" if best[0] == float("inf") else s[best[1]:best[2] + 1]

function minWindow(s, t) {
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  const required = need.size;
  const have = new Map();
  let formed = 0, l = 0, best = [Infinity, 0, 0];
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    have.set(c, (have.get(c) || 0) + 1);
    if (need.has(c) && have.get(c) === need.get(c)) formed++;
    while (formed === required) {
      if (r - l + 1 < best[0]) best = [r - l + 1, l, r];
      const lc = s[l++];
      have.set(lc, have.get(lc) - 1);
      if (need.has(lc) && have.get(lc) < need.get(lc)) formed--;
    }
  }
  return best[0] === Infinity ? "" : s.substring(best[1], best[2] + 1);
}

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
        int required = need.size();
        Map<Character, Integer> have = new HashMap<>();
        int formed = 0, l = 0;
        int[] best = {Integer.MAX_VALUE, 0, 0};
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            have.merge(c, 1, Integer::sum);
            if (need.containsKey(c) && have.get(c).equals(need.get(c))) formed++;
            while (formed == required) {
                if (r - l + 1 < best[0]) { best = new int[]{r - l + 1, l, r}; }
                char lc = s.charAt(l++);
                have.merge(lc, -1, Integer::sum);
                if (need.containsKey(lc) && have.get(lc) < need.get(lc)) formed--;
            }
        }
        return best[0] == Integer.MAX_VALUE ? "" : s.substring(best[1], best[2] + 1);
    }
}

string minWindow(string s, string t) {
    unordered_map<char, int> need;
    for (char c : t) need[c]++;
    int required = need.size();
    unordered_map<char, int> have;
    int formed = 0, l = 0;
    int bestLen = INT_MAX, bestL = 0, bestR = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        char c = s[r];
        have[c]++;
        if (need.count(c) && have[c] == need[c]) formed++;
        while (formed == required) {
            if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; bestR = r; }
            char lc = s[l++];
            have[lc]--;
            if (need.count(lc) && have[lc] < need[lc]) formed--;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);
}

Explanation

We want the shortest slice of s that contains every character of t, counting duplicates. The idea is a sliding window that grows on the right to become valid, then shrinks on the left to become as short as possible.

First we build need, a count of how many of each character t requires. required is how many distinct characters must be fully satisfied. As we scan, have tracks what is inside the window, and formed counts how many characters have reached their needed quantity.

We push r rightward, adding each character. When a character's count in have exactly matches its count in need, we bump formed. Once formed == required, the window covers everything, so we record its length if it is a new best, then shrink from the left to try for something shorter.

While shrinking, dropping a character from the left may break a requirement; if its have count falls below its need count, we lower formed and stop shrinking until the window is valid again.

Example: s = "ADOBECODEBANC", t = "ABC". The window expands and contracts several times; the best valid window ends up being "BANC" at indices 9..12, which is the shortest stretch holding an A, a B, and a C.

Time: O(n + m) Space: O(σ)