Smallest Window Containing All Required Characters

hard string sliding window hash map

Problem

Given strings s and t, return the shortest substring of s that contains every character of t at least as often as t requires (or the empty string if none exists). Slide a window across s: extend the right edge until the window is valid, then contract the left edge as long as it stays valid. Track how many of t's distinct characters currently meet their required count to recognise validity in O(1) per step.

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);
}

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