Minimum Window Substring

hard Strings & Sliding Window

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return the empty string. The answer is guaranteed to be unique when it exists.

Example

s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

The substring "BANC" (positions 9-12) is the shortest substring of s that contains all three characters A, B, and C from t. Other valid windows like "ADOBEC" also contain all of them, but "BANC" is shorter at length 4.

Use a sliding window with two frequency maps — one for the target string t, and one for the current window. Expand the right pointer until the window contains all characters of t (tracked by a 'formed' counter). Once valid, shrink from the left to find the smallest valid window, updating the answer along the way.

Why this works

You need the smallest window in s that contains every character from t. Expand the window rightward until it contains all required characters, then shrink from the left to minimize it. The “formed” counter tracks how many unique characters have met their required count, so you know exactly when the window is valid.

Step by step

Count target frequencies — build a frequency map for t so you know what the window must contain.
Expand the window — move the right pointer forward, updating window frequencies. When a character’s count reaches its target, increment the “formed” counter.
Shrink when valid — once formed == needed, the window has everything. Shrink from the left, recording the smallest valid window found.
Stop shrinking when invalid — when removing a left character drops its count below the target, decrement “formed” and resume expanding.
Return the best — the smallest valid window recorded is the answer.

Time: O(n) Space: O(k)

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) return "";
        Map<Character, Integer> target = new HashMap<>();
        for (char c : t.toCharArray()) {
            target.put(c, target.getOrDefault(c, 0) + 1);
        }
        int needed = target.size();     // unique chars to satisfy
        int formed = 0;
        Map<Character, Integer> window = new HashMap<>();
        int left = 0;
        int[] ans = {-1, 0, 0};
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (target.containsKey(c) && window.get(c).intValue() == target.get(c).intValue()) {
                formed++;              // one more required char fully satisfied
            }
            while (formed == needed) {  // window valid, try to shrink
                if (ans[0] == -1 || right - left + 1 < ans[0]) {
                    ans[0] = right - left + 1;
                    ans[1] = left;
                    ans[2] = right;
                }
                char leftChar = s.charAt(left);
                window.put(leftChar, window.get(leftChar) - 1);
                if (target.containsKey(leftChar) && window.get(leftChar) < target.get(leftChar)) {
                    formed--;          // lost a required char
                }
                left++;
            }
        }
        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }
}

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.empty() || t.empty()) return "";
        unordered_map<char, int> target, window;
        for (char c : t) target[c]++;
        int needed = target.size();     // unique chars to satisfy
        int formed = 0;
        int left = 0;
        int ansLen = INT_MAX, ansLeft = 0;
        for (int right = 0; right < s.size(); right++) {
            window[s[right]]++;
            if (target.count(s[right]) && window[s[right]] == target[s[right]]) {
                formed++;              // one more required char fully satisfied
            }
            while (formed == needed) {  // window valid, try to shrink
                if (right - left + 1 < ansLen) {
                    ansLen = right - left + 1;
                    ansLeft = left;
                }
                window[s[left]]--;
                if (target.count(s[left]) && window[s[left]] < target[s[left]]) {
                    formed--;          // lost a required char
                }
                left++;
            }
        }
        return ansLen == INT_MAX ? "" : s.substr(ansLeft, ansLen);
    }
};

from collections import Counter

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""
    target = Counter(t)
    needed = len(target)          # number of unique chars to satisfy
    formed = 0
    window = {}
    left = 0
    ans = (float('inf'), 0, 0)
    for right in range(len(s)):
        ch = s[right]
        window[ch] = window.get(ch, 0) + 1
        if ch in target and window[ch] == target[ch]:
            formed += 1            # one more required char fully satisfied
        while formed == needed:    # window has all chars, try to shrink
            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)
            window[s[left]] -= 1
            if s[left] in target and window[s[left]] < target[s[left]]:
                formed -= 1        # lost a required char, window no longer valid
            left += 1
    return "" if ans[0] == float('inf') else s[ans[1]:ans[2] + 1]