Problem: Minimum Window Substring

Problem Statement

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 there is no such substring, return the empty string "".

Approach: Variable-Size Sliding Window

This is a "Shortest Window" problem. We want to find the smallest window that satisfies the condition.

1. Count frequencies: Use a map to store characters needed from t.
2. Expand: Move right pointer until the window contains all characters from t.
3. Shrink: Once the condition is met, move left pointer to find the smallest valid window.
4. Repeat: Keep expanding and shrinking until the end of s.

Java Implementation

public String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";
    
    Map<Character, Integer> targetFreq = new HashMap<>();
    for (char c : t.toCharArray()) targetFreq.put(c, targetFreq.getOrDefault(c, 0) + 1);

    int left = 0, minLen = Integer.MAX_VALUE, start = 0, matched = 0;

    for (int right = 0; right < s.length(); right++) {
        char r = s.charAt(right);
        if (targetFreq.containsKey(r)) {
            targetFreq.put(r, targetFreq.get(r) - 1);
            if (targetFreq.get(r) >= 0) matched++;
        }

        // When all characters are matched, try shrinking from the left
        while (matched == t.length()) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }

            char l = s.charAt(left);
            if (targetFreq.containsKey(l)) {
                if (targetFreq.get(l) == 0) matched--;
                targetFreq.put(l, targetFreq.get(l) + 1);
            }
            left++;
        }
    }

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

Complexity Discussion

• Time Complexity: $O(n + m)$ where $n$ is length of s and $m$ is length of t.
• Space Complexity: $O(m)$ to store target frequencies.