Minimum Window Substring

Hardsliding-windowhash-tablestring
Category: Sliding Window
Companies that ask this question:
FacebookAmazonGoogleMicrosoftUber
LeetCode →NeetCode →

Approach

Minimum Window Substring

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.

Examples

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.

Intuition

Use a variable-size sliding window:

  1. Expand right until window contains all characters from t
  2. Contract left while window remains valid, tracking minimum
  3. Repeat until we've processed entire string

Use frequency maps to track required characters and current window contents.

Pattern Recognition

This is a Variable-Size Sliding Window problem with:

  • Expand window until constraint met
  • Contract window while maintaining constraint
  • Track optimal window during contraction

Approach

  1. Count Target: Create frequency map for t
  2. Initialize: left = 0, have = 0, need = unique chars in t
  3. Expand Window (move right):
    • Add s[right] to window count
    • If this satisfies a character requirement, increment have
  4. Contract Window (while valid):
    • Update minimum window if current is smaller
    • Remove s[left], move left++
    • If window becomes invalid, stop contracting
  5. Return minimum window substring

Edge Cases

  • t longer than s (impossible)
  • No valid window exists
  • Entire s is the minimum window
  • Multiple characters with duplicates in t

Complexity Analysis

  • Time Complexity: O(m + n) where m = len(s), n = len(t)
    • Each character in s visited at most twice (once by right, once by left)
    • Building frequency map for t: O(n)
  • Space Complexity: O(m + n)
    • Two frequency maps
    • Each can have at most min(m, n, 256) entries

Solution

java
1class Solution {
2    public String minWindow(String s, String t) {
3        if (s.length() < t.length()) return "";
4
5        // Count characters in t
6        Map<Character, Integer> tCount = new HashMap<>();
7        for (char c : t.toCharArray()) {
8            tCount.put(c, tCount.getOrDefault(c, 0) + 1);
9        }
10
11        int need = tCount.size();  // Unique characters needed
12        int have = 0;              // Unique characters satisfied
13        Map<Character, Integer> windowCount = new HashMap<>();
14
15        int left = 0;
16        int minLen = Integer.MAX_VALUE;
17        int minStart = 0;
18
19        for (int right = 0; right < s.length(); right++) {
20            // Add character to window
21            char c = s.charAt(right);
22            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
23
24            // Check if this character requirement is satisfied
25            if (tCount.containsKey(c) &&
26                windowCount.get(c).equals(tCount.get(c))) {
27                have++;
28            }
29
30            // Contract window while valid
31            while (have == need) {
32                // Update minimum window
33                if (right - left + 1 < minLen) {
34                    minLen = right - left + 1;
35                    minStart = left;
36                }
37
38                // Remove from left
39                char leftChar = s.charAt(left);
40                windowCount.put(leftChar, windowCount.get(leftChar) - 1);
41
42                if (tCount.containsKey(leftChar) &&
43                    windowCount.get(leftChar) < tCount.get(leftChar)) {
44                    have--;
45                }
46
47                left++;
48            }
49        }
50
51        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
52    }
53}
54
Loading visualizer...