Minimum Window Substring

Difficulty: Hard

Problem

Given two strings s and t, find the shortest contiguous piece of s that includes every character of t (counting repeats). Return that piece.

Example

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: Among the pieces of s that include A, B and C, the shortest is BANC.

Brute-force approach

Try all possible substrings of s. For each substring, check if it contains all characters of t. Keep track of the smallest valid substring.

Steps

  1. Generate all substrings of s
  2. For each, check if it contains all of t
  3. Track minimum length valid substring

Time complexity: O(n³) · Space complexity: O(1)

Trade-offs

  • O(n²) substrings to check
  • Each check is O(n) to verify characters
  • Total O(n³) - Very slow for long strings

Optimal approach

Key insight: Use two maps: 'need' for t's characters, 'windowMap' to track current window. Shrink when valid to minimize.

Sliding window: expand until valid, then shrink to find minimum.

Steps

  1. Expand right until window is valid
  2. Window valid when formed == required
  3. Shrink left while valid to minimize
  4. Track minimum valid window

Time complexity: O(n + m) · Space complexity: O(m)

Pseudocode

function minWindow(s, t):
    need = frequency map of t (or array[128])
    window = empty map (or array[128])
    // Approach A: have = 0, required = unique chars in t
    // Approach B: formed = 0, required = length(t)
    left = 0
    minLen = infinity, result = ""
    
    for right from 0 to n-1:
        char = s[right]
        window[char]++
        
        // Approach A: if char in need and window[char] == need[char]: have++
        // Approach B: if window[char] <= need[char]: formed++
        
        while have == required (or formed == required):
            // update result if smaller
            if right - left + 1 < minLen:
                minLen = right - left + 1
                result = s[left..right]
            
            // shrink window
            leftChar = s[left]
            window[leftChar]--
            // Approach A: if leftChar in need and window[leftChar] < need[leftChar]: have--
            // Approach B: if window[leftChar] < need[leftChar]: formed--
            left++
    
    return result

Hints

  • Expand window right until all required characters are found
  • Shrink from left while window is still valid to find minimum
  • Track validity using either: (A) count of unique chars meeting their frequency (have == unique_count), or (B) total matched chars (formed == length(t)). Both are correct O(n) approaches.
  • Use frequency map or array to track character counts in window vs target

Complexity questions

Time for checking all substrings?

O(n³). O(n²) substrings × O(n) to check each = O(n³)

Time for sliding window approach?

O(n + m). O(m) to build need map + O(n) sliding window = O(n + m)

Space for the frequency maps?

O(m). O(m) for need map + O(m) for window counts relevant to t

When do we shrink the window?

When window contains all required chars. Shrink when window contains all required chars to find minimum

Check your understanding of Minimum Window Substring

What is a minimum window substring?

Shortest substring containing all chars of t. Find the smallest substring of s that contains all characters from t.

Given s='ADOBECODEBANC', t='ABC', what's the minimum window?

'BANC'. 'BANC' is the smallest substring containing A, B, and C.

Related problems

Keep practising