Log inSign up
hardleetcodeNot Started

Minimum Window Substring

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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.

Example 1 · Example:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes A, B, and C from string t.

Example 2 · Example:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3 · Example:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both as from t must be included in the window. Since the largest window of s only has one a, return empty string.

Constraints:

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s and t consist of uppercase and lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the expand-and-shrink sliding window template for minimum criteria.
  • Maintain state validity in O(1) with match counters.
  • Extract the substring using stored index pointers without copying substrings repeatedly.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding the smallest contiguous segment satisfying multiset containment constraints.
  • When expanding adds validity and contracting maintains validity.

Algorithmic Decision Tree:

  • Variable-Size Sliding Window
  • Target Multiplicity Counter Matching

Connected Patterns:

Find All Anagrams in a StringLongest Substring Without Repeating CharactersMinimum Window Subsequence

1. Brute Force All Substrings

Intuition

For each start index i and end index j: compute character counts of s[i...j]. If all characters of t are present with sufficient count, check if j - i + 1 < minLen. Return the smallest matching substring.

When to apply: Basic initial explanation.

Algorithm

  1. Populate targetFreq for t.
  2. Loop i from 0 to n - 1:
  3. Loop j from i to n - 1:
  4. If s[i...j] contains t: update minWindow.
  5. Return minWindow.

Interactive Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
required=3 distinct chars ('A','B','C')
Visual state
Values and pointers at this exact step
pointers
S
A
D
O
B
E
C
O
D
E
B
A
N
C
0
↑ i
1
2
3
4
5
6
7
8
9
10
11
12
Check / comparison
formed=3, window='ADOBEC', len=6
Decision / next transition
Advance to next character/state.
Why this step matters

required=3 distinct chars (A,B,C). Expand right until right=5: window=ADOBEC has all 3 required chars.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6 bool isValid(const int sCount[], const int tCount[]) {
7 for (int i = 0; i < 128; ++i) {
8 if (sCount[i] < tCount[i]) return false;
9 }
10 return true;
11 }
12public:
13 std::string minWindow(std::string s, std::string t) {
14 int n = s.size(), m = t.size();
15 if (n < m) return "";
16
17 int tCount[128] = {0};
18 for (char c : t) tCount[(unsigned char)c]++;
19
20 std::string best = "";
21 int minLen = 1e9;
22
23 for (int i = 0; i < n; ++i) {
24 int sCount[128] = {0};
25 for (int j = i; j < n; ++j) {
26 sCount[(unsigned char)s[j]]++;
27 if (j - i + 1 < minLen && isValid(sCount, tCount)) {
28 minLen = j - i + 1;
29 best = s.substr(i, minLen);
30 }
31 }
32 }
33 return best;
34 }
35};
36
37int main() {
38 Solution sol;
39 std::cout << sol.minWindow("ADOBECODEBANC", "ABC") << std::endl; // "BANC"
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N^2 * M) — Tests all N2 substrings with multi-character frequency checks.
  • Space complexity: O(128)

Why Brute Force Doesn't Scale:

Tracking the number of satisfied characters with formed eliminates O(128) array comparison loops.

Using two 128-element static arrays achieves strict O(1) space with zero memory allocations.

2. Filtered Sliding Window (Filtered Index Vector)

Intuition

Create an array filteredS of pairs (index, char) containing only characters from s that exist in t. Run the sliding window algorithm on filteredS. This skips thousands of non-target characters directly in sparse text.

When to apply: When s is extremely large and contains mostly characters irrelevant to t.

Algorithm

  1. Populate targetCount for t.
  2. Filter s into filteredS = [(i, s[i]) for i in s if s[i] in targetCount].
  3. Run sliding window with formed counter over filteredS.
  4. Track minimum window length in original coordinates.
  5. Return substring.

Interactive Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
required=3 distinct chars ('A','B','C')
Visual state
Values and pointers at this exact step
pointers
S
A
D
O
B
E
C
O
D
E
B
A
N
C
0
↑ i
1
2
3
4
5
6
7
8
9
10
11
12
Check / comparison
formed=3, window='ADOBEC', len=6
Decision / next transition
Advance to next character/state.
Why this step matters

required=3 distinct chars (A,B,C). Expand right until right=5: window=ADOBEC has all 3 required chars.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5
6class Solution {
7public:
8 std::string minWindow(std::string s, std::string t) {
9 if (s.empty() || t.empty() || s.size() < t.size()) return "";
10
11 std::unordered_map<char, int> dictT;
12 for (char c : t) dictT[c]++;
13 int required = dictT.size();
14
15 std::vector<std::pair<int, char>> filteredS;
16 for (int i = 0; i < (int)s.size(); ++i) {
17 if (dictT.count(s[i])) {
18 filteredS.push_back({i, s[i]});
19 }
20 }
21
22 int l = 0, r = 0, formed = 0;
23 std::unordered_map<char, int> windowCounts;
24 int minLen = 1e9, startIdx = 0;
25
26 while (r < (int)filteredS.size()) {
27 char c = filteredS[r].second;
28 windowCounts[c]++;
29 if (windowCounts[c] == dictT[c]) formed++;
30
31 while (l <= r && formed == required) {
32 int start = filteredS[l].first;
33 int end = filteredS[r].first;
34 if (end - start + 1 < minLen) {
35 minLen = end - start + 1;
36 startIdx = start;
37 }
38 char leftChar = filteredS[l].second;
39 windowCounts[leftChar]--;
40 if (windowCounts[leftChar] < dictT[leftChar]) formed--;
41 l++;
42 }
43 r++;
44 }
45 return minLen == 1e9 ? "" : s.substr(startIdx, minLen);
46 }
47};
48
49int main() {
50 Solution sol;
51 std::cout << sol.minWindow("ADOBECODEBANC", "ABC") << std::endl; // "BANC"
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(N + M) — Filtering takes O(N), sliding window takes O(|filteredS|).
  • Space complexity: O(N) for filtered list

3. Direct Sliding Window with Formed Counter (O(1) Space)

Intuition

Initialize target[128] and window[128]. Count total distinct characters in t as required. Maintain formed = 0. Expand right pointer over s: when window[s[right]] == target[s[right]], increment formed++. While formed == required, record minimum window coordinates, then shrink left by decrementing window[s[left]]. If window[s[left]] < target[s[left]], decrement formed--. Advance left++.

When to apply: The standard optimal production algorithm combining linear time and O(1) space.

Algorithm

  1. Populate target[128] for t; count distinct target characters required.
  2. Initialize window[128] = {0}, left = 0, right = 0, formed = 0.
  3. Set minLen = Infinity, startIdx = 0.
  4. While right < s.length:
  5. c = s[right]
  6. window[c]++
  7. If target[c] > 0 and window[c] == target[c]: formed++.
  8. While formed == required:
  9. If right - left + 1 < minLen:
  10. minLen = right - left + 1, startIdx = left.
  11. window[s[left]]--
  12. If target[s[left]] > 0 and window[s[left]] < target[s[left]]: formed--.
  13. left++
  14. right++
  15. Return minLen == Infinity ? "" : s.substr(startIdx, minLen).

Dynamic Sliding Window Expansion and Contraction with Frequency Balance

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [A, D, O, B, E, C, O, D, E, B, A, N, C]
Current operationSTEP 1 OF 6
Observation: Target t = "ABC" requires 3 unique character frequencies
Visual state
Values and pointers at this exact step
array
S
A
D
O
B
E
C
0
↑ L=0
1
2
3
4
5
↑ R=5 (First valid window: "ADOBEC")
Variables at this step
L
0
R
5
targetFreq
{"A":1,"B":1,"C":1}
windowFreq
{"A":1,"B":1,"C":1,"D":1,"E":1,"O":1}
satisfiedUnique
3
requiredUnique
3
bestLen
6
bestWindow
ADOBEC
Why this step matters

Observation: Target t = "ABC" requires 3 unique character frequencies. Expand R until all are satisfied: window [0, 5] ("ADOBEC") has A, B, and C.

Decision: Window is valid! Length = 6. Attempt to shrink from left to find smaller sub-window.

Invariant: All target characters present in window.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string minWindow(std::string s, std::string t) {
8 int n = s.size(), m = t.size();
9 if (n < m) return "";
10
11 int target[128] = {0};
12 int required = 0;
13 for (char c : t) {
14 if (target[(unsigned char)c] == 0) required++;
15 target[(unsigned char)c]++;
16 }
17
18 int window[128] = {0};
19 int formed = 0, left = 0, right = 0;
20 int minLen = 1e9, startIdx = 0;
21
22 while (right < n) {
23 unsigned char c = s[right];
24 window[c]++;
25 if (target[c] > 0 && window[c] == target[c]) {
26 formed++;
27 }
28
29 while (left <= right && formed == required) {
30 if (right - left + 1 < minLen) {
31 minLen = right - left + 1;
32 startIdx = left;
33 }
34 unsigned char leftChar = s[left];
35 window[leftChar]--;
36 if (target[leftChar] > 0 && window[leftChar] < target[leftChar]) {
37 formed--;
38 }
39 left++;
40 }
41 right++;
42 }
43
44 return minLen == 1e9 ? "" : s.substr(startIdx, minLen);
45 }
46};
47
48int main() {
49 Solution sol;
50 std::cout << sol.minWindow("ADOBECODEBANC", "ABC") << std::endl; // "BANC"
51 std::cout << sol.minWindow("a", "a") << std::endl; // "a"
52 std::cout << sol.minWindow("a", "aa") << std::endl; // ""
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(N + M) — Every character in s is visited at most twice (once by right, once by left) with O(1) integer operations.
  • Space complexity: O(1) (fixed 128-int arrays)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force All SubstringsO(N^2 * M)O(128)Simple nested loop logic.Quadratic time complexity, impossible on N = 105.
2.Sliding Window with Full Array CheckO(128 * N)O(128)Correct sliding window behavior.Performs 128 array checks at every step.
3.Sliding Window with Formed Counter (Optimal)OptimalO(N + M) strictlyO(1) (fixed 128-element arrays)True linear time, checks validity in O(1) using integer formed tracker.Requires careful increment/decrement of formed.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Incrementing formed on every target character occurrence instead of only when window[c] == target[c].

Pitfall 2:

Rebuilding substrings on each contraction instead of recording start pointer and length.

Crucial Edge Cases to Validate:

  • s.length < t.length: Returns empty string "" immediately.
  • t contains duplicate characters (e.g. t = aa): Condition window[c] == target[c] increments formed only when both as are present.
  • s and t are single characters (s = a, t = a): Evaluated in first step, returns a.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly explain the two phases: expand right to gain validity, then shrink left to optimize length.
  2. Emphasize the formed tracking logic to demonstrate mastery over constant-time state updates.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the formed counter increment ONLY when window[c] == target[c]?

Back to DSA Sheet