Minimum Window Substring

Problem

Given strings s and t, find the smallest substring of s that contains every character of t (including duplicates).

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Python Solution

def min_window(s, t):
    if not t or not s:
        return ""
    need = {}
    for ch in t:
        need[ch] = need.get(ch, 0) + 1
    missing = len(t)
    left = 0
    best_left, best_right = 0, 0
    for right, ch in enumerate(s, 1):
        if need.get(ch, 0) > 0:
            missing -= 1
        need[ch] = need.get(ch, 0) - 1
        while missing == 0:
            if best_right == 0 or right - left < best_right - best_left:
                best_left, best_right = left, right
            need[s[left]] = need.get(s[left], 0) + 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return s[best_left:best_right]

C++ Solution

string minWindow(string s, string t) {
    unordered_map<char, int> need;
    for (char ch : t) need[ch]++;
    int missing = t.size(), left = 0, bestLeft = 0, bestLen = INT_MAX;
    for (int right = 0; right < s.size(); right++) {
        if (need[s[right]] > 0) missing--;
        need[s[right]]--;
        while (missing == 0) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestLeft = left;
            }
            need[s[left]]++;
            if (need[s[left]] > 0) missing++;
            left++;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestLeft, bestLen);
}

Java Solution

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        for (char ch : t.toCharArray()) need.merge(ch, 1, Integer::sum);
        int missing = t.length(), left = 0, bestLeft = 0, bestLen = Integer.MAX_VALUE;
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            if (need.getOrDefault(ch, 0) > 0) missing--;
            need.merge(ch, -1, Integer::sum);
            while (missing == 0) {
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestLeft = left;
                }
                char leftChar = s.charAt(left);
                need.merge(leftChar, 1, Integer::sum);
                if (need.get(leftChar) > 0) missing++;
                left++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestLeft, bestLeft + bestLen);
    }
}

Complexity

Time: O(n + m) — the right pointer and left pointer each move forward at most n times, and t is scanned once to build need. Space: O(k) — where k is the number of distinct characters in t.