Minimum Window Substring problem and solution in Java and Python

Minimum Window Substring is one of the most frequently asked ones in FAANG interviews.

Let’s go step-by-step so it’s clear and intuitive.

---

🧩 Problem: Minimum Window Substring

Question:

Given two strings s (the main string) and t (the target string), find the smallest substring in s that contains all the characters of t (including duplicates). If no such substring exists, return "".

---

Example 1

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

Output:
"BANC"

✅ Because “BANC” is the shortest substring in s containing A, B, and C.

---

Example 2

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

Output:
""

✅ Because s doesn’t have two a’s.

---

🧠 Intuition

You need to find the smallest window (substring) in s that covers all the characters in t.

We can solve this using a sliding window + hash map counting approach.

---

🪜 Step-by-Step Logic (Sliding Window)

1. Create a frequency map of characters in t → need = {A:1, B:1, C:1}
2. Use two pointers (left and right) to represent a window in s.
3. Expand the right pointer to include characters until all needed ones are covered.
4. Once valid, shrink the window from the left to find the minimum possible substring.
5. Keep track of the smallest window found so far.

---

✅ Java Solution

import java.util.*;

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";

        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray())
            need.put(c, need.getOrDefault(c, 0) + 1);

        int required = need.size();
        int formed = 0;

        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int minLen = Integer.MAX_VALUE;
        int start = 0;

        while (right < s.length()) {
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);

            if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue())
                formed++;

            while (left <= right && formed == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }

                char d = s.charAt(left);
                window.put(d, window.get(d) - 1);
                if (need.containsKey(d) && window.get(d) < need.get(d))
                    formed--;
                left++;
            }
            right++;
        }

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

---

✅ Python Solution

def minWindow(s: str, t: str) -> str:
    if len(t) > len(s):
        return ""
    
    from collections import Counter
    need = Counter(t)
    window = {}
    
    have, needCount = 0, len(need)
    res, resLen = [-1, -1], float("inf")
    left = 0
    
    for right, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        
        if c in need and window[c] == need[c]:
            have += 1
        
        while have == needCount:
            # update result
            if (right - left + 1) < resLen:
                res = [left, right]
                resLen = right - left + 1
            
            # shrink from left
            window[s[left]] -= 1
            if s[left] in need and window[s[left]] < need[s[left]]:
                have -= 1
            left += 1
    
    l, r = res
    return s[l:r+1] if resLen != float("inf") else ""

---

⚙️ Complexity

Type	Time	Space
Time Complexity	O(	s	+	t	)	Each character processed at most twice
Space Complexity	O(	s	+	t	)	For hash maps

---

🧠 To Explain to a Kid

Imagine you’re looking for the smallest backpack that can carry all your school items (A, B, C).

You keep:

• Adding items (expanding the window)
• Once you have everything, you try to remove extra space (shrinking from left)
• You note down the smallest backpack that still fits all items.

That’s the “minimum window substring”! 🎒✨

---

💬 Common Variations

Variation	Description
Minimum Window Subsequence	Same idea, but characters must appear in order (not contiguous).
Longest Substring Without Repeating Characters	Uses similar sliding window logic but tracks duplicates instead of matching a target.
Permutation in String	Checks if s2 contains a permutation of s1 (window of exact size of s1).

---