Approach Summary
Expand the window to include all required characters, then shrink from the left while the window remains valid. Track counts with two frequency maps.
Practice Mode
3 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Sliding Window with Target Frequency Counter (Optimal) | O(m + n) | O(n) | Track remaining unfulfilled character count; contract window from left whenever all characters are present. |
| 2 Approach 2: Naive Substring Validation with Frequency Counter (Baseline) | O(m² * alphabet) | O(alphabet) | Generates all substrings of s, checking if each contains all required character frequencies of t. |
| 3 Approach 2: Naive Substring Validation with Frequency Counter (Baseline) | O(m² * alphabet) | O(alphabet) | Generates all substrings of s, checking if each contains all required character frequencies of t. |
Step 1: Baseline
Approach 1: Sliding Window with Target Frequency Counter (Optimal)
Time: O(m + n)
Space: O(n)
Initialize a frequency map for t. Track the number of distinct characters whose required count has been satisfied. When required == 0, the current window [left, right] is a valid match. Update minLen, then shrink left to find the tightest possible valid boundary.
Approach 1: Sliding Window with Target Frequency Counter (Optimal) Implementation
Approach 1: Sliding Window with Target Frequency Counter (Optimal)
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> tFreq = new HashMap<>();
for (char c : t.toCharArray()) {
tFreq.put(c, tFreq.getOrDefault(c, 0) + 1);
}
int left = 0, required = tFreq.size(), minLen = Integer.MAX_VALUE;
String result = "";
for (int right = 0; right < s.length(); right++) {
if (tFreq.containsKey(s.charAt(right))) {
tFreq.put(s.charAt(right), tFreq.get(s.charAt(right)) - 1);
if (tFreq.get(s.charAt(right)) == 0) required--;
}
while (required == 0) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
result = s.substring(left, right + 1);
}
if (tFreq.containsKey(s.charAt(left))) {
tFreq.put(s.charAt(left), tFreq.get(s.charAt(left)) + 1);
if (tFreq.get(s.charAt(left)) > 0) required++;
}
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : result;
}
}class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> tFreq;
for (int i = 0; i < t.size(); i++) tFreq[t[i]]++;
int left = 0, minLen = INT_MAX, required = tFreq.size(), minStart = 0;
for (int right = 0; right < s.size(); right++) {
if (tFreq.find(s[right]) != tFreq.end()) {
tFreq[s[right]]--;
if (tFreq[s[right]] == 0) required--;
}
while (required == 0) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
if (tFreq.find(s[left]) != tFreq.end()) {
tFreq[s[left]]++;
if (tFreq[s[left]] > 0) required++;
}
left++;
}
}
return minLen == INT_MAX ? "" : s.substr(minStart, minLen);
}
};class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(s) < len(t):
return ""
t_freq = {}
for c in t:
t_freq[c] = t_freq.get(c, 0) + 1
required = len(t_freq)
left = 0
min_len = float('inf')
min_start = 0
for right in range(len(s)):
if s[right] in t_freq:
t_freq[s[right]] -= 1
if t_freq[s[right]] == 0:
required -= 1
while required == 0:
if right - left + 1 < min_len:
min_len = right - left + 1
min_start = left
if s[left] in t_freq:
t_freq[s[left]] += 1
if t_freq[s[left]] > 0:
required += 1
left += 1
return "" if min_len == float('inf') else s[min_start:min_start + min_len]function minWindow(s, t) {
if (s.length < t.length) return "";
const tFreq = new Map();
for (const c of t) tFreq.set(c, (tFreq.get(c) || 0) + 1);
let left = 0, required = tFreq.size, minLen = Infinity, minStart = 0;
for (let right = 0; right < s.length; right++) {
const c = s[right];
if (tFreq.has(c)) {
tFreq.set(c, tFreq.get(c) - 1);
if (tFreq.get(c) === 0) required--;
}
while (required === 0) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
const leftC = s[left];
if (tFreq.has(leftC)) {
tFreq.set(leftC, tFreq.get(leftC) + 1);
if (tFreq.get(leftC) > 0) required++;
}
left++;
}
}
return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
} Step 2
Approach 2: Naive Substring Validation with Frequency Counter (Baseline)
Time: O(m² * alphabet)
Space: O(alphabet)
Iterates through all possible substrings s[i..j]. For each candidate, compares character counts with target string t. Among all valid candidates that satisfy all character quotas, records the minimum length substring.
Approach 2: Naive Substring Validation with Frequency Counter (Baseline) Implementation
Approach 2: Naive Substring Validation with Frequency Counter (Baseline)
class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";
int[] target = new int[128];
for (char c : t.toCharArray()) target[c]++;
int minLen = Integer.MAX_VALUE;
String ans = "";
for (int i = 0; i < s.length(); i++) {
int[] curr = new int[128];
for (int j = i; j < s.length(); j++) {
curr[s.charAt(j)]++;
boolean ok = true;
for (int c = 0; c < 128; c++) {
if (target[c] > 0 && curr[c] < target[c]) { ok = false; break; }
}
if (ok) {
if (j - i + 1 < minLen) {
minLen = j - i + 1;
ans = s.substring(i, j + 1);
}
break;
}
}
}
return ans;
}
}class Solution {
public:
string minWindow(string s, string t) {
if (s.size() < t.size()) return "";
vector<int> target(128, 0);
for (char c : t) target[c]++;
int minLen = INT_MAX;
string ans = "";
for (int i = 0; i < s.size(); i++) {
vector<int> curr(128, 0);
for (int j = i; j < s.size(); j++) {
curr[s[j]]++;
bool ok = true;
for (int c = 0; c < 128; c++) {
if (target[c] > 0 && curr[c] < target[c]) { ok = false; break; }
}
if (ok) {
if (j - i + 1 < minLen) {
minLen = j - i + 1;
ans = s.substr(i, j - i + 1);
}
break;
}
}
}
return ans;
}
};from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t or len(s) < len(t): return ""
target = Counter(t)
min_len = float('inf')
ans = ""
for i in range(len(s)):
curr = Counter()
for j in range(i, len(s)):
curr[s[j]] += 1
if j - i + 1 >= len(t):
if all(curr[c] >= target[c] for c in target):
if (j - i + 1) < min_len:
min_len = j - i + 1
ans = s[i:j + 1]
break
return ansfunction minWindow(s, t) {
if (s.length < t.length) return "";
const target = {};
for (const c of t) target[c] = (target[c] || 0) + 1;
let minLen = Infinity, ans = "";
for (let i = 0; i < s.length; i++) {
const curr = {};
for (let j = i; j < s.length; j++) {
curr[s[j]] = (curr[s[j]] || 0) + 1;
let valid = true;
for (const k in target) {
if ((curr[k] || 0) < target[k]) { valid = false; break; }
}
if (valid) {
if (j - i + 1 < minLen) {
minLen = j - i + 1;
ans = s.slice(i, j + 1);
}
break;
}
}
}
return ans;
} Step 2: Most Optimized
Approach 2: Naive Substring Validation with Frequency Counter (Baseline)
Time: O(m² * alphabet)
Space: O(alphabet)
Iterates through all possible substrings s[i..j]. For each candidate, compares character counts with target string t. Among all valid candidates that satisfy all character quotas, records the minimum length substring.
Approach 2: Naive Substring Validation with Frequency Counter (Baseline) Implementation
Approach 2: Naive Substring Validation with Frequency Counter (Baseline)
class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";
int[] target = new int[128];
for (char c : t.toCharArray()) target[c]++;
int minLen = Integer.MAX_VALUE;
String ans = "";
for (int i = 0; i < s.length(); i++) {
int[] curr = new int[128];
for (int j = i; j < s.length(); j++) {
curr[s.charAt(j)]++;
boolean ok = true;
for (int c = 0; c < 128; c++) {
if (target[c] > 0 && curr[c] < target[c]) { ok = false; break; }
}
if (ok) {
if (j - i + 1 < minLen) {
minLen = j - i + 1;
ans = s.substring(i, j + 1);
}
break;
}
}
}
return ans;
}
}class Solution {
public:
string minWindow(string s, string t) {
if (s.size() < t.size()) return "";
vector<int> target(128, 0);
for (char c : t) target[c]++;
int minLen = INT_MAX;
string ans = "";
for (int i = 0; i < s.size(); i++) {
vector<int> curr(128, 0);
for (int j = i; j < s.size(); j++) {
curr[s[j]]++;
bool ok = true;
for (int c = 0; c < 128; c++) {
if (target[c] > 0 && curr[c] < target[c]) { ok = false; break; }
}
if (ok) {
if (j - i + 1 < minLen) {
minLen = j - i + 1;
ans = s.substr(i, j - i + 1);
}
break;
}
}
}
return ans;
}
};from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t or len(s) < len(t): return ""
target = Counter(t)
min_len = float('inf')
ans = ""
for i in range(len(s)):
curr = Counter()
for j in range(i, len(s)):
curr[s[j]] += 1
if j - i + 1 >= len(t):
if all(curr[c] >= target[c] for c in target):
if (j - i + 1) < min_len:
min_len = j - i + 1
ans = s[i:j + 1]
break
return ansfunction minWindow(s, t) {
if (s.length < t.length) return "";
const target = {};
for (const c of t) target[c] = (target[c] || 0) + 1;
let minLen = Infinity, ans = "";
for (let i = 0; i < s.length; i++) {
const curr = {};
for (let j = i; j < s.length; j++) {
curr[s[j]] = (curr[s[j]] || 0) + 1;
let valid = true;
for (const k in target) {
if ((curr[k] || 0) < target[k]) { valid = false; break; }
}
if (valid) {
if (j - i + 1 < minLen) {
minLen = j - i + 1;
ans = s.slice(i, j + 1);
}
break;
}
}
}
return ans;
}Edge Cases to Watch
- s is shorter than t (returns "" immediately)
- s equals t (e.g. s = "a", t = "a"; returns "a")
- t contains duplicate characters (e.g. t = "AABC"; window must contain at least two 'A's)
- No window contains all characters (returns "")
Algorithmic Pattern
View Pattern Guide →
Master the Sliding Window Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Sliding Window pattern.
Framework: Sliding Window • Interview Prep: Tested at FAANG •
Explore all Sliding Window problems & invariants →
How to Recognize This Pattern
- Minimum window containing all of another string
Complexity Analysis
Time Complexity
O(n + m)
Space Complexity
O(m)
Tags
String Hash Map Sliding Window
Frequently Asked Questions
What is the optimal time and space complexity for Minimum Window Substring?
The optimal solution for Minimum Window Substring achieves O(n + m) runtime complexity and requires O(m) auxiliary space. Time complexity is O(m + n) since right scans s once and left catches up once. Space complexity is O(n) where n is the number of distinct characters in t (bounded by character set size).
How do I identify that Minimum Window Substring requires the Sliding Window pattern?
In technical interviews, look for key problem signals: Minimum window containing all of another string. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Sliding Window strategy.
What critical edge cases must be handled in Minimum Window Substring?
Essential edge cases to verify include: s is shorter than t (returns "" immediately); s equals t (e.g. s = "a", t = "a"; returns "a"); t contains duplicate characters (e.g. t = "AABC"; window must contain at least two 'A's); No window contains all characters (returns ""). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Minimum Window Substring?
Minimum Window Substring is a Hard-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Facebook, Amazon, Google, Uber.