Minimum Window Substring

Problem Statement

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

Examples:

s	t	Result	Explanation
"ADOBECODEBANC"	"ABC"	"BANC"	Smallest window containing A, B, and C
"a"	"a"	"a"	Exact match
"a"	"aa"	""	Not enough characters in s

Constraints:

• 1 <= s.length, t.length <= 10^5
• s and t consist of uppercase and lowercase English letters
• The answer is guaranteed to be unique when it exists

This is a classic sliding window problem and one of the most frequently asked string questions in technical interviews.

---

Key Insight

The brute force approach checks every possible substring — there are O(n²) of them, and verifying each takes O(m) time. We can do dramatically better by observing that once we find a valid window, we don’t need to start over. Instead, we slide the window: expand the right boundary to include more characters, and contract the left boundary to minimize the window.

The critical optimization is a formed counter. Instead of comparing two frequency maps on every step (which costs O(m) per comparison), we track how many unique characters in t have reached their required frequency in the current window. When formed == required, the window is valid — and we know this in O(1).

---

Approach 1: Brute Force — O(n² × m)

The naive solution generates all substrings of s and checks each for containing all characters of t:

String minWindow(String s, String t) {
    if (s.isEmpty() || t.isEmpty() || s.length() < t.length()) {
        return "";
    }

    // Build frequency map for t
    var tFreq = new HashMap<Character, Integer>();
    for (char c : t.toCharArray()) {
        tFreq.merge(c, 1, Integer::sum);
    }

    int minLen = Integer.MAX_VALUE;
    int minStart = 0;

    for (int i = 0; i < s.length(); i++) {
        var windowFreq = new HashMap<Character, Integer>();
        for (int j = i; j < s.length(); j++) {
            windowFreq.merge(s.charAt(j), 1, Integer::sum);

            // Check if window contains all chars of t
            if (containsAll(windowFreq, tFreq) && (j - i + 1) < minLen) {
                minLen = j - i + 1;
                minStart = i;
            }
        }
    }

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

boolean containsAll(Map<Character, Integer> window, Map<Character, Integer> target) {
    for (var entry : target.entrySet()) {
        if (window.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
            return false;
        }
    }
    return true;
}

Why this is too slow: For s.length() = 10^5, we’d perform roughly 10^10 operations. The containsAll check runs up to O(m) for each of the O(n²) substrings. Interview verdict: demonstrates understanding but unacceptable for production.

---

Approach 2: Sliding Window — O(n + m) time, O(m) space

Algorithm Walkthrough

The sliding window technique maintains a window [left, right] and moves these pointers to find the optimal answer:

1. Build a frequency map for t — this tells us what we need
2. Initialize left = 0, right = 0, formed = 0, required = number of unique chars in t
3. Expand by moving right:
   • Add s[right] to the window frequency map
   • If this character’s count now matches t’s requirement, increment formed
4. Contract when formed == required:
   • The current window is valid — record it if it’s the smallest seen
   • Remove s[left] from the window map
   • If this drops below t’s requirement, decrement formed
   • Move left forward
5. Repeat until right reaches the end of s

The formed counter is the key innovation. Instead of comparing entire maps (O(m) per check), we maintain a running count of how many characters are “satisfied.” This makes validity checking O(1).

Implementation

record WindowResult(int start, int end) {
    int length() { return end - start + 1; }
}

String minWindow(String s, String t) {
    if (s.isEmpty() || t.isEmpty() || s.length() < t.length()) {
        return "";
    }

    // Frequency map for t
    var tFreq = new HashMap<Character, Integer>();
    for (char c : t.toCharArray()) {
        tFreq.merge(c, 1, Integer::sum);
    }

    int required = tFreq.size();  // Number of unique chars in t we need
    int formed = 0;               // How many unique chars currently satisfied

    // Window frequency map
    var windowFreq = new HashMap<Character, Integer>();

    // Best answer tracking
    int bestLen = Integer.MAX_VALUE;
    int bestStart = 0;

    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        // Expand: add s[right] to window
        char rightChar = s.charAt(right);
        windowFreq.merge(rightChar, 1, Integer::sum);

        // Check if this character's frequency now matches t's requirement
        if (tFreq.containsKey(rightChar)
                && windowFreq.get(rightChar).intValue() == tFreq.get(rightChar).intValue()) {
            formed++;
        }

        // Contract: try to shrink from the left while window is valid
        while (formed == required) {
            // Update best window
            int windowLen = right - left + 1;
            if (windowLen < bestLen) {
                bestLen = windowLen;
                bestStart = left;
            }

            // Remove s[left] from window
            char leftChar = s.charAt(left);
            windowFreq.merge(leftChar, -1, Integer::sum);

            if (tFreq.containsKey(leftChar)
                    && windowFreq.get(leftChar) < tFreq.get(leftChar)) {
                formed--;
            }

            left++;
        }
    }

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

Detailed Walkthrough

Let’s trace s = "ADOBECODEBANC", t = "ABC":

t requires: {A:1, B:1, C:1}   required = 3

Step 1: Expand right →
  [A] D O B E C O D E B A N C
   L
   R
  window = {A:1}  formed = 1 (A satisfied)

Step 2-3: Expand right →
  [A D O] B E C O D E B A N C
   L
       R
  window = {A:1, D:1, O:1}  formed = 1

Step 4: Expand right →
  [A D O B] E C O D E B A N C
   L
         R
  window = {A:1, D:1, O:1, B:1}  formed = 2 (B satisfied)

Step 5: Expand right →
  [A D O B E] C O D E B A N C
   L
           R
  window = {A:1, D:1, O:1, B:1, E:1}  formed = 2

Step 6: Expand right → formed == 3!
  [A D O B E C] O D E B A N C
   L
             R
  window = {A:1, D:1, O:1, B:1, E:1, C:1}  formed = 3 ✓
  → Record "ADOBEC" (length 6)

  Contract left → remove A → formed drops to 2
   D O B E C  O D E B A N C
   L
             R

Step 7-9: Keep expanding right →
  ...
  D O B E C O D E B  A N C
                   L
                         R
  At some point, we hit formed == 3 again

Step 10: formed == 3 at window "BANC"
  A D O B E C O D E [B A N C]
                      L     R
  → Record "BANC" (length 4) — new best!

  Contract left → remove B → formed drops to 2
  Right reaches end → done

Answer: "BANC"

---

Optimization: Filtered String

When s is much longer than t, many characters in s are irrelevant — they don’t appear in t at all. We can create a filtered list containing only positions of relevant characters:

String minWindowFiltered(String s, String t) {
    if (s.isEmpty() || t.isEmpty() || s.length() < t.length()) {
        return "";
    }

    var tFreq = new HashMap<Character, Integer>();
    for (char c : t.toCharArray()) {
        tFreq.merge(c, 1, Integer::sum);
    }

    // Build filtered list: only positions with chars in t
    record CharPos(int index, char ch) {}
    var filtered = new ArrayList<CharPos>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (tFreq.containsKey(c)) {
            filtered.add(new CharPos(i, c));
        }
    }

    int required = tFreq.size();
    int formed = 0;
    var windowFreq = new HashMap<Character, Integer>();

    int bestLen = Integer.MAX_VALUE;
    int bestStart = 0;

    int left = 0;
    for (int right = 0; right < filtered.size(); right++) {
        char rightChar = filtered.get(right).ch();
        windowFreq.merge(rightChar, 1, Integer::sum);

        if (windowFreq.get(rightChar).intValue() == tFreq.get(rightChar).intValue()) {
            formed++;
        }

        while (formed == required) {
            int windowStart = filtered.get(left).index();
            int windowEnd = filtered.get(right).index();
            int windowLen = windowEnd - windowStart + 1;

            if (windowLen < bestLen) {
                bestLen = windowLen;
                bestStart = windowStart;
            }

            char leftChar = filtered.get(left).ch();
            windowFreq.merge(leftChar, -1, Integer::sum);
            if (windowFreq.get(leftChar) < tFreq.get(leftChar)) {
                formed--;
            }
            left++;
        }
    }

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

When does this help? If s has length 100,000 but only 500 characters appear in t, the inner loop iterates over 500 entries instead of 100,000. The worst case is unchanged, but practical performance can improve dramatically for sparse matches.

---

Complexity Analysis

Sliding Window (Approach 2):

• Time: O(|s| + |t|)
  • Building the frequency map for t: O(|t|)
  • Each character in s is visited at most twice — once when right expands over it, once when left contracts past it
  • Total: O(2|s| + |t|) = O(|s| + |t|)
• Space: O(|s| + |t|)
  • Frequency maps store at most O(|s| + |t|) entries
  • In practice, bounded by the alphabet size (52 for upper+lowercase English)

Filtered Optimization:

• Time: O(|s| + |t|) worst case, but inner loop runs over filtered.size() ≤ |s|
• Space: O(|s| + |t|) for the filtered list and frequency maps

---

Edge Cases

1. t longer than s: s = "a", t = "aa" → return "" immediately. The string simply cannot contain enough characters.

2. s == t: s = "ABC", t = "ABC" → return "ABC". The entire string is the minimum window.

3. Duplicate characters in t: t = "AABC" requires two As in the window. The frequency map correctly tracks this — formed only increments when the window count equals the required count, not just when a character is present.

4. No valid window: s = "XYZW", t = "ABC" → return "". The formed counter never reaches required.

5. Single character strings: s = "a", t = "a" → return "a". The window starts and ends at index 0.

6. All same characters: s = "AAAA", t = "AA" → return "AA". The window shrinks to exactly two consecutive As.

---

Common Variations

The sliding window technique is a versatile template that adapts to many substring problems:

Longest Substring with At Most K Distinct Characters

• Instead of matching a target frequency, maintain a window where the number of distinct characters ≤ K
• Contract when distinct count exceeds K
• Track maximum window instead of minimum

Substring with Concatenation of All Words (LeetCode 30)

• Given a list of words (all same length), find starting indices where concatenation of all words appears
• Uses a sliding window of size wordCount × wordLength
• Frequency map tracks words instead of characters

Template Pattern

Most sliding window problems follow this skeleton:

int left = 0;
for (int right = 0; right < s.length(); right++) {
    // 1. Expand: process s[right]

    // 2. Check validity condition
    while (windowIsValid()) {
        // 3. Update answer (for minimum problems)
        // 4. Contract: remove s[left], move left++
    }
    // For maximum problems, update answer here instead
}

The key differences between problems are:

• What makes a window valid (formed == required, distinct ≤ K, sum ≤ target)
• Whether we want minimum or maximum (update inside vs. outside the while loop)
• What data structure tracks the window state (frequency map, set, counter)

---

Interviewer Tips

Start with brute force. Even if you know the optimal approach, briefly mention the O(n² × m) solution. It shows you understand the problem space and gives you a baseline to improve upon. Say: “The naive approach checks all O(n²) substrings, each in O(m) time. We can do better with a sliding window.”

The formed counter is the key insight. When explaining your approach, emphasize why you use a counter instead of comparing maps. The interviewer wants to see that you understand the optimization from O(m) per validity check to O(1). Walk through the logic: “I only increment formed when a character’s window count exactly equals its required count, so I know in constant time whether the window contains everything.”

Draw the window on the whiteboard. Use brackets to show the current window, mark left and right pointers, and show the formed count at each step. Visual candidates stand out.

Handle the .intValue() comparison carefully. In Java, Integer objects cached for values -128 to 127 can be compared with ==, but larger values cannot. Always use .intValue() or .equals() when comparing Integer wrapper types. This is a common source of bugs that interviewers specifically look for.

Follow-up questions to prepare for:

• “Can you do this with O(1) space?” → Not really — the frequency map is necessary, but it’s bounded by alphabet size (effectively O(1) for fixed alphabets)
• “What if we want the smallest window containing all distinct characters of s itself?” → Same technique, but t becomes the set of unique characters in s
• “What about finding all minimum windows, not just one?” → Track all windows with length equal to bestLen during the contraction phase