Minimum Window Substring — Practice

Problem

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.

Examples

Example 1

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

Output: "BANC"

Explanation: "BANC" is the smallest substring of s containing all of A, B, and C.

Example 2

Input: s = "a", t = "a"

Output: "a"

Explanation: The entire string is the minimum window.

Example 3

Input: s = "a", t = "aa"

Output: ""

Explanation: t requires two a's, s only has one — no valid window exists.

Constraints

•1 <= s.length, t.length <= 10^5
•s and t consist of uppercase and lowercase English letters

Hints

Hint 1

This is the variable-size sliding window pattern at its hardest: the window must expand to satisfy a condition, then shrink as much as possible while still satisfying it.

Hint 2

Track how many of t's required characters (with correct counts) are currently satisfied in the window — a single integer counter, not a full re-scan, can tell you when the window is valid.

Hint 3

Once the window is valid, shrink from the left greedily until it's no longer valid, recording the smallest valid window seen along the way.

Solutions

public String minWindowBruteForce(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);

    String best = "";
    for (int i = 0; i < s.length(); i++) {
        for (int j = i; j < s.length(); j++) {
            String candidate = s.substring(i, j + 1);
            if (containsAll(candidate, need) && (best.isEmpty() || candidate.length() < best.length())) {
                best = candidate;
            }
        }
    }
    return best;
}
private boolean containsAll(String candidate, Map<Character, Integer> need) {
    Map<Character, Integer> count = new HashMap<>();
    for (char c : candidate.toCharArray()) count.merge(c, 1, Integer::sum);
    for (var entry : need.entrySet()) {
        if (count.getOrDefault(entry.getKey(), 0) < entry.getValue()) return false;
    }
    return true;
}

Time: O(n^3) · Space: O(t.length())