How do you solve Minimum Window Substring?

Use a sliding window with two pointers. Expand the right pointer to include characters until the window contains all characters of t. Then, move the left pointer to shrink the window while maintaining validity. Keep track of the smallest window found. Return the substring corresponding to this window or an empty string if none exists.

What pattern does Minimum Window Substring use?

The Pattern: Sliding Window (Variable Size with Frequency Counting) The Heuristic: When searching for a minimum or maximum substring containing all required elements, maintain counts of needed characters and expand the window until valid, then contract from the left to discard unnecessary characters, ensuring each character is processed at most twice.

Minimum Window Substring — Sliding Window

Q: What is the time complexity of Minimum Window Substring?

O(n). Each character in s is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it. Hash map operations are O(1) on average, resulting in linear time complexity.

Problem

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

1 ≤ s.length, t.length ≤ 10⁵
s and t consist of English letters.

Example

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

Output: "BANC"

A brute-force approach would check every substring of s to see if it contains all characters of t, which is O(n^3) and infeasible for large inputs. The optimal approach uses a sliding window to expand and contract over s, tracking character counts to efficiently find the smallest valid window. Starting with pointers at the beginning, the window expands until it contains all characters of t. Then it contracts from the left to remove unnecessary characters, updating the minimum window length. This process repeats until the right pointer reaches the end of s. The critical insight is maintaining counts of required characters and only contracting when the window is valid, enabling an O(n) time solution.

Approach

Straightforward Solution

A brute-force approach enumerates all substrings of s and checks if each contains t, resulting in O(n^3) time due to substring generation and character counting, which is too slow.

Core Observation

The problem reduces to finding the smallest substring of s that contains all characters of t with correct multiplicities. This requires tracking character frequencies and efficiently checking window validity.

Path to Optimal

Preview

Recognizing the problem as a substring containment problem with multiplicities suggests a sliding window approach…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a sliding window with two pointers. Expand the right pointer to include characters until the window contains all characters of t…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each character in s is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it. Hash map operations are O(1) on average, resulting in linear time complexity.

Space

O(m)

Auxiliary space is used for two hash maps storing character counts: one for t and one for the current window. The size of these maps is bounded by the number of unique characters in t, which is at most m = len(t). This space is necessary to track character frequencies.

Solution

Python

1class Solution:
  def minWindow(self, s: str, t: str) -> str:
      if t == "":
          return ""
5
      count_t = {}
      for c in t:
          count_t[c] = 1 + count_t.get(c, 0)
      
      have, need = 0, len(count_t)
      res, res_len = [-1, -1], float("infinity")
      l = 0
      window = {}
      
      for r in range(len(s)):
          c = s[r]
          window[c] = 1 + window.get(c, 0)
          
          if c in count_t and window[c] == count_t[c]:
              have += 1
          
          while have == need:
              if (r - l + 1) < res_len:
                  res = [l, r]
                  res_len = (r - l + 1)
26
              window[s[l]] -= 1
              if s[l] in count_t and window[s[l]] < count_t[s[l]]:
                  have -= 1
              l += 1
      
      l, r = res
      return s[l:r + 1] if res_len != float("infinity") else ""

Step-by-Step Solution

1

Build Frequency Map for Target String and Initialize Sliding Window State

6count_t = {}
7for c in t:
8    count_t[c] = 1 + count_t.get(c, 0)
10have, need = 0, len(count_t)
11res, res_len = [-1, -1], float("infinity")
12l = 0
13window = {}

Objective

To count the frequency of each character in t and set up variables to track the sliding window and result.

Key Insight

Counting the required characters upfront allows the algorithm to know exactly when the window contains all needed characters. Initializing counters for how many unique characters have been satisfied ('have') versus how many are needed ('need') enables efficient validity checks. The window map tracks the current counts of characters in the sliding window, and the result variables store the best window found so far.

Interview Quick-Check

Core Logic

Building a frequency map for t enables constant-time checks of whether the current window meets the required character counts.

State & Boundaries

Initialize 'have' to 0 and 'need' to the number of unique characters in t to track window validity.

Common Pitfalls & Bugs

Forgetting to initialize the window map or result variables correctly can lead to incorrect window tracking or failure to update the minimal window.

2

Expand the Window by Moving Right Pointer and Update Counts

To iterate over s with the right pointer, expanding the window and updating character counts to track when the window satisfies the requirements.

3

Contract the Window by Moving Left Pointer to Find Minimum Valid Substring

To shrink the window from the left while it remains valid, updating the result with the smallest window found.

4

Return the Minimum Window Substring or Empty String if None Found

To extract and return the substring corresponding to the smallest valid window found, or return an empty string if no valid window exists.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 10 Critical

have, need = 0, len(count_t)

Initialize 'have' and 'need' counters for window validity.

'have' tracks how many unique characters currently meet required counts, while 'need' is the total unique characters needed; this enables efficient validity checks.

Line 19 Critical

if c in count_t and window[c] == count_t[c]:

Check if current character count matches required count in t.

Only when the window count equals the required count for a character does it contribute to satisfying the overall requirement, so this condition triggers incrementing 'have'.

Line 22 Critical

while have == need:

While the window is valid, attempt to contract it from the left.

Contracting the window when valid helps find the minimal window containing all required characters by removing unnecessary characters from the left.

Full line-by-line criticality + rationale for all 24 lines available on Pro.

Test Your Understanding

Why does the algorithm only contract the window when it contains all required characters, and how does this ensure the minimal window is found?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Minimum Window Substring from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Minimum Window Substring drill

or drill a free problem

1	`class Solution:`
2	`def minWindow(self, s: str, t: str) -> str:`
3	`if t == "":`
4	`return ""`
5
6	`count_t = {}`
7	`for c in t:`
8	`count_t[c] = 1 + count_t.get(c, 0)`
9
10	`have, need = 0, len(count_t)`
11	`res, res_len = [-1, -1], float("infinity")`
12	`l = 0`
13	`window = {}`
14
15	`for r in range(len(s)):`
16	`c = s[r]`
17	`window[c] = 1 + window.get(c, 0)`
18
19	`if c in count_t and window[c] == count_t[c]:`
20	`have += 1`
21
22	`while have == need:`
23	`if (r - l + 1) < res_len:`
24	`res = [l, r]`
25	`res_len = (r - l + 1)`
26
27	`window[s[l]] -= 1`
28	`if s[l] in count_t and window[s[l]] < count_t[s[l]]:`
29	`have -= 1`
30	`l += 1`
31
32	`l, r = res`
33	`return s[l:r + 1] if res_len != float("infinity") else ""`

6	`count_t = {}`
7	`for c in t:`
8	`count_t[c] = 1 + count_t.get(c, 0)`
10	`have, need = 0, len(count_t)`
11	`res, res_len = [-1, -1], float("infinity")`
12	`l = 0`
13	`window = {}`