Crack the Backend

Problem Statement

Given two strings s and t, return the minimum window substring of s that contains every character in t (including duplicates). If there is no such window, return the empty string "".

The window must contain at least the same count of each character as t (e.g. if t = "AAB", the window must have at least 2 A's and 1 B).
If t is longer than s, return "". If multiple minimum windows exist, return any one of them.
Characters in s that are not in t can appear in the window; we only care about satisfying the required counts for t.

Key Observations

We need a variable-size sliding window that "covers" t: the window has, for each character in t, at least as many occurrences as in t. We can build a frequency map for t and maintain the window's counts; "required" can be tracked as the number of distinct characters that are still under their target count (or we check if all targets are met).
Expand with right until the window covers t; then shrink from left while the window still covers t, to get the smallest valid window ending at right. Track the minimum length and the corresponding substring.
When we add a character that is in t, we update the window count; when that count reaches the target for that character, we can decrement a "required" counter. When required becomes 0, the window covers t.

Approach

High-level: Maintain a window [left, right] and frequency counts for t and for the current window. Expand right until the window contains all characters of t (with correct counts); then shrink left while the window still covers t, and record the minimum window. Return the substring for that minimum window.

Steps:

Build freq for t (how many of each char we need). Maintain window counts and a "required" count (e.g. number of distinct chars that are still short of target).
For each right: add s[right] to window. If s[right] is in t and window now meets the target for that char, decrement required. When required == 0, the window covers t.
While the window still covers t, update the minimum length and substring, then remove s[left] and left++.
Return the minimum substring (or "" if never found).

Implementation

Java

public String minWindow(String s, String t) {

    if (t.length() > s.length()) {
        return "";
    }

    Map<Character, Integer> need = new HashMap<>();

    for (char c : t.toCharArray()) {
        need.merge(c, 1, Integer::sum);
    }

    int required = need.size(), left = 0, minStart = 0, minLen = Integer.MAX_VALUE;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        if (need.containsKey(c)) {
            need.merge(c, -1, Integer::sum);

            if (need.get(c) == 0) {
                required--;
            }
        }

        while (required == 0) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }

            char l = s.charAt(left);

            if (need.containsKey(l)) {
                if (need.get(l) == 0) {
                    required++;
                }

                need.merge(l, 1, Integer::sum);
            }

            left++;
        }
    }

    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}

Test Cases

Example 1

Input

s = "ADOBECODEBANC", t = "ABC"

Expected

"BANC"

Explanation

Minimum window containing A, B, C.

Complexity Analysis

Time: O(|s| + |t|).
Space: O(1) or O(|t|).

Follow-ups

Return all minimum windows; handle duplicate chars in t correctly.