33. Minimum Window Substring

🔗 LeetCode Problem: 76. Minimum Window Substring
📊 Difficulty: Hard
🏷️ Topics: Hash Table, String, Sliding Window

Problem Statement

Given two strings s and t of lengths m and n respectively, 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 "".

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints: - m == s.length - n == t.length - 1 <= m, n <= 10^5 - s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

🎨 Visual Understanding

The Problem Visualized

s = "ADOBECODEBANC"
t = "ABC"

Find minimum substring containing all characters from t:

A D O B E C O D E B A N C
^     ^   ^              → "ADOBEC" contains A, B, C (length 6)
        ^   ^     ^ ^    → "ODEBANC" contains A, B, C (length 7)
                  ^ ^ ^  → "BANC" contains A, B, C (length 4) ✓

Answer: "BANC" (shortest window)

Key Observation: Sliding Window

Use two pointers to create a sliding window:

1. Expand window (right pointer) until all characters found
2. Contract window (left pointer) while still valid
3. Track minimum window during contraction
4. Repeat until right reaches end

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

Step 1: Expand until valid
[A D O B E C] → Contains A, B, C ✓ (length 6)

Step 2: Contract while valid
  [D O B E C] → Missing A ✗
Stop, record "ADOBEC"

Step 3: Continue expanding
  [D O B E C O D E B A] → Contains A, B, C ✓

Step 4: Contract while valid
      [B E C O D E B A] → Missing all
      Continue...
                [B A N C] → Contains A, B, C ✓ (length 4)

Why Sliding Window Works

Key insight: 
- Right pointer expands to find valid window
- Left pointer contracts to minimize window
- We never need to backtrack

Time: O(m + n) where m = s.length, n = t.length
Each character visited at most twice (once by right, once by left)

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Check all possible substrings:
1. Generate all substrings of s
2. For each substring, check if it contains all characters from t
3. Track minimum valid substring

Why This Works: - Checks all possibilities - Guaranteed to find answer if exists - Simple to understand

Why This Fails Requirements: - Time complexity O(m² × n) or worse - Too many substrings to check - Checking each substring is expensive - Not acceptable for interviews

Implementation

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

    String minWindow = "";
    int minLen = Integer.MAX_VALUE;

    // Try all substrings
    for (int i = 0; i < s.length(); i++) {
        for (int j = i + 1; j <= s.length(); j++) {
            String substring = s.substring(i, j);

            // Check if this substring contains all chars from t
            if (containsAllChars(substring, t)) {
                if (substring.length() < minLen) {
                    minLen = substring.length();
                    minWindow = substring;
                }
            }
        }
    }

    return minWindow;
}

private boolean containsAllChars(String s, String t) {
    Map<Character, Integer> tCount = new HashMap<>();
    for (char c : t.toCharArray()) {
        tCount.put(c, tCount.getOrDefault(c, 0) + 1);
    }

    for (char c : s.toCharArray()) {
        if (tCount.containsKey(c)) {
            tCount.put(c, tCount.get(c) - 1);
            if (tCount.get(c) == 0) {
                tCount.remove(c);
            }
        }
    }

    return tCount.isEmpty();
}

⏰ Time: O(m² × n) - m² substrings, each checked in O(n)
💾 Space: O(n) - for character counting

✅ Approach 2: Sliding Window with HashMap (Optimal)

The Breakthrough Insight 💡

Core Logic:

Use sliding window with two pointers + frequency maps:

Data structures:
- tMap: frequency of each character in t (target)
- windowMap: frequency of characters in current window
- required: total unique characters needed from t
- formed: how many unique characters satisfied in window

Algorithm:
1. Build tMap from string t
2. Expand window (right++) until valid (formed == required)
3. Contract window (left++) while still valid
4. Track minimum window during contraction
5. Repeat until right reaches end

Visual Explanation:

s = "ADOBECODEBANC", t = "ABC"

tMap = {A:1, B:1, C:1}
required = 3 (need A, B, C)

Window: [A D O B E C]
windowMap = {A:1, D:1, O:1, B:1, E:1, C:1}
formed = 3 (have A, B, C) ✓

Contract left:
Window: [D O B E C]
windowMap = {D:1, O:1, B:1, E:1, C:1}
formed = 2 (missing A) ✗

Can't contract more, record window "ADOBEC"
Continue expanding...

Key Variables:

required: Number of unique characters in t that need to be present
formed: Number of unique characters in current window with desired frequency

Example: t = "AABC"
tMap = {A:2, B:1, C:1}
required = 3 (need A, B, C as unique chars)

Window has A:1, B:1, C:1 → formed = 2 (A not satisfied yet)
Window has A:2, B:1, C:1 → formed = 3 (all satisfied) ✓

Implementation

public String minWindow(String s, String t) {
    if (s.length() == 0 || t.length() == 0) {
        return "";
    }

    // Dictionary to keep count of all unique characters in t
    Map<Character, Integer> tMap = new HashMap<>();
    for (char c : t.toCharArray()) {
        tMap.put(c, tMap.getOrDefault(c, 0) + 1);
    }

    int required = tMap.size();  // Unique characters in t
    int left = 0, right = 0;
    int formed = 0;  // Unique characters in window with desired frequency

    // Dictionary to keep count of characters in current window
    Map<Character, Integer> windowMap = new HashMap<>();

    // Result: [window length, left, right]
    int[] result = {-1, 0, 0};

    while (right < s.length()) {
        // Expand window by adding character from right
        char c = s.charAt(right);
        windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);

        // Check if frequency of current character matches desired frequency in t
        if (tMap.containsKey(c) && 
            windowMap.get(c).intValue() == tMap.get(c).intValue()) {
            formed++;
        }

        // Try to contract window until it's no longer valid
        while (left <= right && formed == required) {
            // Save smallest window
            if (result[0] == -1 || right - left + 1 < result[0]) {
                result[0] = right - left + 1;
                result[1] = left;
                result[2] = right;
            }

            // Character at left pointer is no longer part of window
            char leftChar = s.charAt(left);
            windowMap.put(leftChar, windowMap.get(leftChar) - 1);

            // Check if this character is no longer satisfied
            if (tMap.containsKey(leftChar) && 
                windowMap.get(leftChar) < tMap.get(leftChar)) {
                formed--;
            }

            // Move left pointer ahead for next iteration
            left++;
        }

        // Expand window
        right++;
    }

    return result[0] == -1 ? "" : s.substring(result[1], result[2] + 1);
}

⏰ Time: O(m + n) - each character visited at most twice
💾 Space: O(m + n) - for HashMaps

🔍 Step-by-Step Execution

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

Initial State:
═══════════════════════════════════════════════════════════════════
s = "ADOBECODEBANC"
t = "ABC"

tMap = {A:1, B:1, C:1}
required = 3
left = 0, right = 0
formed = 0
minWindow = ""


Step 1: right=0, char='A'
═══════════════════════════════════════════════════════════════════
Window: [A]
windowMap = {A:1}
A is in tMap and count matches → formed = 1

Try to contract? formed(1) != required(3) → No
Move right++


Step 2: right=1, char='D'
═══════════════════════════════════════════════════════════════════
Window: [A D]
windowMap = {A:1, D:1}
D not in tMap → formed = 1

Move right++


Step 3: right=2, char='O'
═══════════════════════════════════════════════════════════════════
Window: [A D O]
windowMap = {A:1, D:1, O:1}
O not in tMap → formed = 1

Move right++


Step 4: right=3, char='B'
═══════════════════════════════════════════════════════════════════
Window: [A D O B]
windowMap = {A:1, D:1, O:1, B:1}
B is in tMap and count matches → formed = 2

Move right++


Step 5: right=4, char='E'
═══════════════════════════════════════════════════════════════════
Window: [A D O B E]
windowMap = {A:1, D:1, O:1, B:1, E:1}
E not in tMap → formed = 2

Move right++


Step 6: right=5, char='C'
═══════════════════════════════════════════════════════════════════
Window: [A D O B E C]
windowMap = {A:1, D:1, O:1, B:1, E:1, C:1}
C is in tMap and count matches → formed = 3 ✓

Now formed == required, try to contract:

Contract iteration 1: left=0
  Current window "ADOBEC" length 6
  Update minWindow = "ADOBEC"
  Remove 'A': windowMap = {A:0, D:1, O:1, B:1, E:1, C:1}
  A count drops below required → formed = 2
  left = 1
  Stop contracting (formed != required)

Move right++


Steps 7-9: right=6,7,8 (chars 'O','D','E')
═══════════════════════════════════════════════════════════════════
Window expands but formed stays at 2 (missing A)
windowMap updated but not valid yet


Step 10: right=9, char='B'
═══════════════════════════════════════════════════════════════════
Window: [D O B E C O D E B]
windowMap = {D:2, O:2, B:2, E:2, C:1}
B count now 2, but only need 1 → formed = 2

Move right++


Step 11: right=10, char='A'
═══════════════════════════════════════════════════════════════════
Window: [D O B E C O D E B A]
windowMap = {D:2, O:2, B:2, E:2, C:1, A:1}
A is in tMap and count matches → formed = 3 ✓

Try to contract:

Contract iteration 1: left=1
  Current window "DOBECODEBA" length 10
  Not better than "ADOBEC" (6)
  Remove 'D': formed = 3 (still valid)
  left = 2

Contract iteration 2: left=2
  Remove 'O': formed = 3 (still valid)
  left = 3

Contract iteration 3: left=3
  Remove 'B': windowMap B count becomes 1
  B still satisfied → formed = 3 (still valid)
  left = 4

Contract iteration 4: left=4
  Remove 'E': formed = 3 (still valid)
  left = 5

Contract iteration 5: left=5
  Remove 'C': windowMap C count becomes 0
  C no longer satisfied → formed = 2
  Stop contracting

Move right++


Step 12: right=11, char='N'
═══════════════════════════════════════════════════════════════════
Window: [O D E B A N]
N not in tMap → formed = 2

Move right++


Step 13: right=12, char='C'
═══════════════════════════════════════════════════════════════════
Window: [O D E B A N C]
windowMap gets C:1
C is in tMap and count matches → formed = 3 ✓

Try to contract:

Contract: Keep removing until we can't
Eventually get to: [B A N C]
Window "BANC" length 4 < 6
Update minWindow = "BANC"


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: "BANC"
═══════════════════════════════════════════════════════════════════

🔍 Edge Cases

Case 1: t longer than s
Input: s = "a", t = "aa"
Output: ""
Explanation: Cannot find two 'a's in s

Case 2: Exact match
Input: s = "a", t = "a"
Output: "a"
Explanation: Entire string is the answer

Case 3: t contains duplicates
Input: s = "ADOBECODEBANC", t = "AABC"
Output: "ADOBECODEBA"
Explanation: Need two A's

Case 4: Multiple valid windows
Input: s = "ABCABC", t = "ABC"
Output: "ABC"
Explanation: Two windows of same length, return first

Case 5: No valid window
Input: s = "a", t = "b"
Output: ""

Case 6: All of s needed
Input: s = "ABC", t = "ABC"
Output: "ABC"

Case 7: Extra characters in s
Input: s = "AXXXXBC", t = "ABC"
Output: "AXXXXBC"

Case 8: Window at end
Input: s = "XYZABC", t = "ABC"
Output: "ABC"

Common Mistakes

Mistake 1: Not handling character frequency correctly
❌ Wrong: 
    if (windowMap.containsKey(c)) {
        formed++;  // Always increment
    }
✓ Right: 
    if (tMap.containsKey(c) && 
        windowMap.get(c).equals(tMap.get(c))) {
        formed++;  // Only when frequency matches
    }
Reason: Need exact frequency match, not just presence

Mistake 2: Wrong contraction condition
❌ Wrong: 
    while (left < right) {  // Missing formed check
        ...
    }
✓ Right: 
    while (left <= right && formed == required) {
        ...
    }
Reason: Only contract when window is valid

Mistake 3: Not tracking minimum window correctly
❌ Wrong: 
    String minWindow = s.substring(left, right + 1);
    // Directly assigning without comparison
✓ Right: 
    if (result[0] == -1 || right - left + 1 < result[0]) {
        result[0] = right - left + 1;
        result[1] = left;
        result[2] = right;
    }
Reason: Need to track minimum, not just current

Mistake 4: Forgetting to expand window
❌ Wrong: 
    while (right < s.length()) {
        ...
        // Missing right++
    }
✓ Right: 
    while (right < s.length()) {
        ...
        right++;
    }
Reason: Must move right pointer to expand

Mistake 5: Wrong formed decrement
❌ Wrong: 
    windowMap.put(leftChar, windowMap.get(leftChar) - 1);
    if (windowMap.get(leftChar) == 0) {
        formed--;
    }
✓ Right: 
    windowMap.put(leftChar, windowMap.get(leftChar) - 1);
    if (tMap.containsKey(leftChar) && 
        windowMap.get(leftChar) < tMap.get(leftChar)) {
        formed--;
    }
Reason: Only decrement when frequency drops below required

Mistake 6: Integer comparison with ==
❌ Wrong: 
    if (windowMap.get(c) == tMap.get(c)) {
        // May fail due to Integer caching
    }
✓ Right: 
    if (windowMap.get(c).intValue() == tMap.get(c).intValue()) {
        // Or use .equals()
    }
Reason: Integer objects need .equals() or .intValue()

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(m² × n)
  Space: O(n)
  Use: Only for understanding, too slow

Approach 2: Sliding Window (RECOMMENDED)
  Time: O(m + n)
  Space: O(m + n)
  Use: Optimal solution, best for interviews

🔑 The Core Insight

Sliding Window Pattern:
1. Use two pointers (left, right) to form window
2. Expand window (right++) until valid
3. Contract window (left++) while still valid
4. Track optimum during contraction
5. Repeat until right reaches end

Key Variables:
- tMap: Target character frequencies
- windowMap: Current window character frequencies
- required: Number of unique characters needed
- formed: Number of unique characters satisfied

Valid Window:
formed == required
(All unique characters from t have desired frequency in window)

Time Complexity:
- Each character visited at most twice
- Once by right pointer (expand)
- Once by left pointer (contract)
- Total: O(m + n)

🎯 Pattern Recognition

Problem Type: Substring with Constraints
Core Pattern: Sliding Window + HashMap

When to Apply:
✓ Finding substring with specific properties
✓ Need to track character frequencies
✓ Can use two pointers (window)
✓ Want O(n) time complexity

Key Techniques:
→ Sliding window with two pointers
→ HashMap for character counting
→ Expand until valid
→ Contract while valid
→ Track optimum during contraction

Related Problems:
- Longest Substring Without Repeating Characters (LC 3)
- Longest Substring with At Most K Distinct Characters (LC 340)
- Find All Anagrams in String (LC 438)
- Substring with Concatenation of All Words (LC 30)

🧠 Interview Strategy

Step 1: "Need minimum substring containing all chars from t"
Step 2: "Use sliding window with two pointers"
Step 3: "Track character frequencies with HashMap"
Step 4: "Expand until valid, contract while valid"
Step 5: "O(m + n) time, each char visited twice max"

Key Points to Mention:
- Sliding window technique
- Two HashMaps for counting
- formed vs required concept
- Contract only when window is valid
- Track minimum during contraction
- O(m + n) time complexity

📝 Quick Revision Notes

🎯 Core Concept:

Use sliding window with two pointers and HashMaps for frequency counting. Expand until valid, contract while valid, track minimum.

⚡ Quick Implementation:

public String minWindow(String s, String t) {
    int left = 0;
    int right = 0;

    // Place all characters of t in tMap
    HashMap<Character, Integer> tMap = new HashMap<>();        
    for(char ch : t.toCharArray()) {
        tMap.put(ch, tMap.getOrDefault(ch, 0) + 1);
    }
    int needed = tMap.size(); // actual number of unique chars in target t
    int formed = 0; // actual number of unique chars in source s

    // For results
    int size = Integer.MAX_VALUE;
    int start = 0;
    String res = "";

    // Place characters of the current window in a hashmap
    HashMap<Character, Integer> windowMap = new HashMap<>();        
    while (right < s.length()) {
        // Put the current char being examined in source map (windowMap)
        // which is always character at index right
        char ch = s.charAt(right);
        windowMap.put(ch, windowMap.getOrDefault(ch, 0) + 1);

        // check if the count of the current char (ch) in the windowMap 
        // matches the count of the same char in the tMap
        if(tMap.containsKey(ch) && windowMap.get(ch).intValue() == tMap.get(ch).intValue()) { // Gotch2 - without intValue, numbers never become equal for very large numbers
            formed++; // no of unique chars matched till now
        }

        // If no of chars match, save the result and now start shrinking 
        // the window by reducing the left till you find a difference in char count
        while(needed == formed && left <= right) {
            // First save the best result before proceeding
            if (right - left + 1 < size) {
                size = right - left + 1;
                // res = s.substring(left, right + 1); // Gotch1 - gets Memory Limit Exception
                start = left;
            }

            // Since window at left side is reduced, windowMap also should be updated.
            windowMap.put(s.charAt(left), windowMap.get(s.charAt(left)) - 1);                

            // since there is a change in windowMap, check if still windowMap contains all chars of tMap
            // Similar condition as above. But, check char removed which is at left
            if(tMap.containsKey(s.charAt(left)) && windowMap.get(s.charAt(left)).intValue() < tMap.get(s.charAt(left)).intValue()) {
                formed--;
            }

            left++;
        }

        right++;
    }

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

🔑 Key Insights:

Two HashMaps: tMap (target), windowMap (current window)
Two counters: required (unique chars needed), formed (unique chars satisfied)
Expand: right++, add to window until formed == required
Contract: left++, remove from window while formed == required
Track minimum: Update result during contraction phase
Valid window: formed == required (all chars with correct frequency)
Time: O(m + n) - each char visited at most twice
Space: O(m + n) - for HashMaps
Key: Only contract when valid, track min while contracting

🎪 Memory Aid:

"Expand till VALID, contract while VALID, track MIN!"
Think: "Two pointers slide, HashMaps count, formed == required"

Longest Substring Without Repeating Characters (LC 3)
Find All Anagrams in a String (LC 438)
Longest Substring with At Most K Distinct Characters (LC 340)
Substring with Concatenation of All Words (LC 30)

Happy practicing! 🎯

33. Minimum Window Substring

Problem Statement

🎨 Visual Understanding

The Problem Visualized

Key Observation: Sliding Window

Why Sliding Window Works

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Implementation

✅ Approach 2: Sliding Window with HashMap (Optimal)

The Breakthrough Insight 💡

Implementation

🔍 Step-by-Step Execution

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

🔍 Edge Cases

Common Mistakes

🎯 Key Takeaways

⚡ Algorithm Comparison

🔑 The Core Insight

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

Related Patterns