Minimum Window Substring

Difficulty: Hard

Problem

Given strings s and t, return the minimum window substring of s that contains all characters of t.

Example

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring containing A, B, C 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)