Minimum Window Substring solution and explanation
IBM
9 more videos on this problem
Minimum Window Substring - Airbnb Interview Question - Leetcode 76NeetCode · 25:41 · 525K views
L12. Minimum Window Substring | 2 Pointers and Sliding Window Playlisttake U forward · 27:06 · 328K views
Minimum Window Substring | Google | Leetcode 76codestorywithMIK · 38:06 · 58K views
Minimum Window Substring | Sliding Window | LeetCodeAlgosWithMichael · 18:00 · 46K views
Minimum Window Substring | Leetcode #76Techdose · 16:57 · 13K views
Minimum Window Substring (LeetCode 76) | Interview Essential | Sliding Window + Two PointersNikhil Lohia · 21:35 · 11K views
[Java] Leetcode 76. Minimum Window Substring [Sliding Window #8]Eric Programming · 14:16 · 11K views
76. Minimum Window Substring | 5 Improvizations | Sliding WindowAryan Mittal · 38:46 · 6K views
MINIMUM WINDOW SUBSTRING | LEETCODE # 76 | PYTHON SOLUTIONCracking FAANG · 28:08 · 6K views
76. Minimum Window Substring | LeetCode | Java SolutionShrayansh Jain · 14:24 · 6K views
The problem
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:
Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window.
Example 3:
Input: s = "a", t = "aa" Output: "" Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.
Constraints:
m == s.lengthn == t.length1 <= m, n <= 105sandtconsist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n) time?
Approach overview
Problem Overview: You are given two strings s and t. The goal is to find the smallest substring of s that contains every character from t (including duplicates). If no such substring exists, return an empty string.
Approach 1: Generate All Substrings and Check Validity (O(n² * k) time, O(k) space)
This brute force strategy generates every possible substring of s using two nested loops. For each substring, build a frequency map and compare it with the character requirements of t. If the substring contains all required characters with correct counts, update the minimum length window. The main cost comes from repeatedly validating substrings, which requires scanning character counts. Time complexity is O(n² * k), where k is the number of unique characters in t. Space complexity is O(k) for the frequency map. This approach demonstrates the basic idea but becomes impractical for large inputs because it checks too many substrings.
Approach 2: Sliding Window with Hashmap (O(n) time, O(k) space)
The optimal solution uses the sliding window technique with a frequency map from a hash table. First build a map storing how many times each character appears in t. Use two pointers (left and right) to represent a window over s. Expand the window by moving right and updating counts when characters from t appear. Once the window contains all required characters, try shrinking it by moving left while still maintaining validity. Each valid window update checks if its length is smaller than the best result. Every character enters and leaves the window at most once, which keeps the total work linear. The time complexity is O(n) and space complexity is O(k), where k is the number of distinct characters in t. This pattern is common in string problems that require the smallest or largest valid substring.
Recommended for interviews: Interviewers expect the sliding window solution. Starting with the brute force method shows you understand the problem constraints and correctness. The sliding window with a hashmap demonstrates strong algorithmic thinking, reducing the search space from all substrings to a dynamically adjusted window while maintaining character counts in constant time.
Approach 1: Sliding Window with Hashmap
This approach uses a sliding window (two-pointer technique) along with hash maps to keep track of characters. One hash map counts all characters in the string "t", while another counts the current characters inside the window from the string "s". We expand the right pointer to include characters until we have a valid window containing all characters from "t", and then contract the left pointer to minimize the window size.
from collections import Counter
def minWindow(s: str, t: str) -> str:
required = Counter(t)
window = Counter()
left = 0
min_len = float('inf')
min_start = 0
count = 0
for right, char in enumerate(s):
window[char] += 1
if window[char] <= required[char]:
count += 1
while count == len(t):
if right - left + 1 < min_len:
min_len = right - left + 1
min_start = left
window[s[left]] -= 1
if window[s[left]] < required[s[left]]:
count -= 1
left += 1
return "" if min_len > len(s) else s[min_start:min_start + min_len]import java.util.HashMap;
import java.util.Map;
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> required = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) required.put(c, required.getOrDefault(c, 0) + 1);
int left = 0, minLen = Integer.MAX_VALUE, minStart = 0, count = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c) <= required.get(c)) count++;
while (count == t.length()) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
char cl = s.charAt(left++);
window.put(cl, window.get(cl) - 1);
if (window.get(cl) < required.get(cl)) count--;
}
}
return minLen > s.length() ? "" : s.substring(minStart, minStart + minLen);
}
}#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> required, window;
for(char c : t) ++required[c];
int left = 0, count = 0, min_len = s.size() + 1, min_start = 0;
for(int right = 0; right < s.size(); ++right) {
char c = s[right];
window[c]++;
if (window[c] <= required[c]) ++count;
while(count == t.size()) {
if (right - left + 1 < min_len) {
min_len = right - left + 1;
min_start = left;
}
char lc = s[left++];
if (window[lc] > 0) {
window[lc]--;
if (window[lc] < required[lc]) --count;
}
}
}
return min_len > s.size() ? "" : s.substr(min_start, min_len);
}
};function minWindow(s, t) {
const required = {};
for (let c of t) {
required[c] = (required[c] || 0) + 1;
}
const window = {};
let left = 0, minLen = Infinity, minStart = 0, count = 0;
for (let right = 0; right < s.length; right++) {
let char = s[right];
window[char] = (window[char] || 0) + 1;
if (window[char] <= required[char]) count++;
while (count === t.length) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
let charLeft = s[left++];
window[charLeft]--;
if (window[charLeft] < (required[charLeft] || 0)) count--;
}
}
return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
}#include <stdio.h>
#include <string.h>
#define CHAR_COUNT 128
char* minWindow(char* s, char* t) {
int slen = strlen(s), tlen = strlen(t);
if(slen < tlen) return "";
int required[CHAR_COUNT] = {0}, window[CHAR_COUNT] = {0};
for(int i = 0; i < tlen; i++) required[t[i]]++;
int left = 0, minLen = slen + 1, minStart = 0, count = 0;
for(int right = 0; right < slen; right++) {
char c = s[right];
window[c]++;
if (window[c] <= required[c]) count++;
while(count == tlen) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
char cl = s[left++];
if (window[cl] > 0) {
window[cl]--;
if (window[cl] < required[cl]) count--;
}
}
}
return minLen > slen ? "" : strndup(s + minStart, minLen);
}using System;
using System.Collections.Generic;
public class Solution {
public string MinWindow(string s, string t) {
Dictionary<char, int> required = new Dictionary<char, int>();
Dictionary<char, int> window = new Dictionary<char, int>();
foreach(char c in t) {
if (!required.ContainsKey(c)) required[c] = 0;
required[c]++;
}
int left = 0, minLen = int.MaxValue, minStart = 0, count = 0;
for(int right = 0; right < s.Length; right++) {
char c = s[right];
if (!window.ContainsKey(c)) window[c] = 0;
window[c]++;
if (window[c] <= required[c]) count++;
while(count == t.Length) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
char cl = s[left++];
if (window[cl] > 0) {
window[cl]--;
if (window[cl] < required[cl]) count--;
}
}
}
return minLen > s.Length ? "" : s.Substring(minStart, minLen);
}
}The Python solution uses Counter from the collections module to efficiently count character occurrences. The sliding window technique incrementally finds a valid window and attempts to minimize it whenever a complete valid form is found.
Time Complexity: O(m + n) since every character in "s" and "t" is evaluated at most twice.
Space Complexity: O(1) as the count is dependent on the character space (fixed size).
Approach 2: Generate All Substrings and Check Validity
This alternative approach generates all possible substrings of "s" and checks each to see if it contains all the characters of "t" (including counts). Although not optimal, it serves as a conceptual fundamental check against the sliding window optimal approach by explicitly comparing substrings.
def minWindow(s: str, t: str) -> str:
from collections import Counter
if len(s) < len(t): return ""
required = Counter(t)
result = ""
min_len = float('inf')
def isValid(required, window):
for char in required:
if window.get(char, 0) < required[char]:
return False
return True
for start in range(len(s)):
window = Counter()
for end in range(start, len(s)):
window[s[end]] += 1
if end - start + 1 >= len(t) and isValid(required, window):
if end - start + 1 < min_len:
min_len = end - start + 1
result = s[start:end+1]
break
return resultimport java.util.HashMap;
public class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";
HashMap<Character, Integer> required = new HashMap<>();
for (char c : t.toCharArray()) required.put(c, required.getOrDefault(c, 0) + 1);
String result = "";
int min_len = s.length() + 1;
for (int start = 0; start < s.length(); start++) {
HashMap<Character, Integer> window = new HashMap<>();
for (int end = start; end < s.length(); end++) {
char c = s.charAt(end);
window.put(c, window.getOrDefault(c, 0) + 1);
if (end - start + 1 >= t.length() && isValid(required, window)) {
if (end - start + 1 < min_len) {
min_len = end - start + 1;
result = s.substring(start, end + 1);
}
break;
}
}
}
return result;
}
private boolean isValid(HashMap<Character, Integer> required, HashMap<Character, Integer> window) {
for (Character c : required.keySet()) {
if (window.getOrDefault(c, 0) < required.get(c)) return false;
}
return true;
}
}#include <string>
#include <unordered_map>
using namespace std;
bool isValid(const unordered_map<char, int>& required, const unordered_map<char, int>& window) {
for (auto& it : required) {
if (window.at(it.first) < it.second) return false;
}
return true;
}
string minWindow(string s, string t) {
unordered_map<char, int> required, window;
for (char c : t) required[c]++;
string result = "";
int min_len = s.size() + 1;
for (int start = 0; start < s.size(); ++start) {
window.clear();
for (int end = start; end < s.size(); ++end) {
window[s[end]]++;
if (end - start + 1 >= t.length() && isValid(required, window)) {
if (end - start + 1 < min_len) {
min_len = end - start + 1;
result = s.substr(start, min_len);
}
break;
}
}
}
return result;
}function minWindow(s, t) {
if (s.length < t.length) return "";
const required = {};
for (let char of t) {
required[char] = (required[char] || 0) + 1;
}
let minLen = Infinity;
let result = "";
const isValid = (required, window) => {
for (let key in required) {
if (window[key] < required[key] || !window[key]) return false;
}
return true;
};
for (let start = 0; start < s.length; ++start) {
const window = {};
for (let end = start; end < s.length; ++end) {
const char = s[end];
window[char] = (window[char] || 0) + 1;
if (end - start + 1 >= t.length && isValid(required, window)) {
if (end - start + 1 < minLen) {
minLen = end - start + 1;
result = s.slice(start, end + 1);
}
break;
}
}
}
return result;
}#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define CHAR_COUNT 128
bool isValid(char* s, char* t, int start, int end) {
int required[CHAR_COUNT] = {0}, window[CHAR_COUNT] = {0};
for(int i = 0; i < strlen(t); i++) required[t[i]]++;
for(int i = start; i < end; i++) window[s[i]]++;
for(int i = 0; i < CHAR_COUNT; i++) {
if (window[i] < required[i]) return false;
}
return true;
}
char* minWindow(char* s, char* t) {
int slen = strlen(s), tlen = strlen(t);
if (slen < tlen) return "";
int minLen = slen + 1, start = 0, end = 0;
char* result = "";
for (start = 0; start < slen; start++) {
for (end = start + tlen; end <= slen; end++) {
if (isValid(s, t, start, end) && (end - start) < minLen) {
minLen = end - start;
result = strndup(s + start, minLen);
}
}
}
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public string MinWindow(string s, string t) {
if (s.Length < t.Length) return "";
Dictionary<char, int> required = new Dictionary<char, int>();
foreach (char c in t) {
if (!required.ContainsKey(c)) required[c] = 0;
required[c]++;
}
string result = "";
int min_len = int.MaxValue;
for (int start = 0; start < s.Length; ++start) {
Dictionary<char, int> window = new Dictionary<char, int>();
for (int end = start; end < s.Length; ++end) {
char c = s[end];
if (!window.ContainsKey(c)) window[c] = 0;
window[c]++;
if (end - start + 1 >= t.Length && IsValid(required, window)) {
if (end - start + 1 < min_len) {
min_len = end - start + 1;
result = s.Substring(start, end - start + 1);
}
break;
}
}
}
return result;
}
private bool IsValid(Dictionary<char, int> required, Dictionary<char, int> window) {
foreach (var kvp in required) {
if (window.GetValueOrDefault(kvp.Key) < kvp.Value) return false;
}
return true;
}
}The Python approach builds possible substrings while maintaining their character counts. It evaluates using a custom "isValid" function to ensure suitability against "t". Substrings meeting the criteria update potential minimum outcomes.
Time Complexity: O(m^2 * n) from nested loop orders and count evaluations.
Space Complexity: O(1) with counters leveraging fixed character range.
Approach 3: Counting + Two Pointers
We use a hash table or array need to count the occurrences of each character in string t, and another hash table or array window to count the occurrences of each character in the sliding window. Additionally, we define two pointers l and r to point to the left and right boundaries of the window, a variable cnt to represent how many characters from t are already included in the window, and variables k and mi to represent the starting position and length of the minimum window substring.
We traverse the string s from left to right. For the current character s[r]:
- We add it to the window, i.e.,
window[s[r]] = window[s[r]] + 1. Ifneed[s[r]] geq window[s[r]], it meanss[r]is a "necessary character", and we incrementcntby one. - If
cntequals the length oft, it means the window already contains all characters fromt, and we can try to update the starting position and length of the minimum window substring. Ifr - l + 1 < mi, it means the current window represents a shorter substring, so we updatemi = r - l + 1andk = l. - Then, we try to move the left boundary
l. Ifneed[s[l]] geq window[s[l]], it meanss[l]is a "necessary character", and moving the left boundary will removes[l]from the window. Therefore, we need to decrementcntby one, updatewindow[s[l]] = window[s[l]] - 1, and movelone position to the right. - If
cntis not equal to the length oft, it means the window does not yet contain all characters fromt, so we do not need to move the left boundary. Instead, we moverone position to the right and continue traversing.
After the traversal, if no minimum window substring is found, return an empty string. Otherwise, return s[k:k+mi].
The time complexity is O(m + n), and the space complexity is O(|\Sigma|). Here, m and n are the lengths of strings s and t, respectively; and |\Sigma| is the size of the character set, which is 128 in this problem.
function minWindow(s: string, t: string): string {
const need: number[] = Array(128).fill(0);
const window: number[] = Array(128).fill(0);
for (let i = 0; i < t.length; i++) {
need[t.charCodeAt(i)]++;
}
const [m, n] = [s.length, t.length];
let [k, mi, cnt] = [-1, m + 1, 0];
for (let l = 0, r = 0; r < m; r++) {
let c = s.charCodeAt(r);
if (++window[c] <= need[c]) {
cnt++;
}
while (cnt === n) {
if (r - l + 1 < mi) {
mi = r - l + 1;
k = l;
}
c = s.charCodeAt(l);
if (window[c] <= need[c]) {
cnt--;
}
window[c]--;
l++;
}
}
return k < 0 ? '' : s.substring(k, k + mi);
}func minWindow(s string, t string) string {
need := make([]int, 128)
window := make([]int, 128)
for i := 0; i < len(t); i++ {
need[t[i]]++
}
m, n := len(s), len(t)
k, mi, cnt := -1, m+1, 0
for l, r := 0, 0; r < m; r++ {
c := s[r]
if window[c]++; window[c] <= need[c] {
cnt++
}
for cnt == n {
if r-l+1 < mi {
mi = r - l + 1
k = l
}
c = s[l]
if window[c] <= need[c] {
cnt--
}
window[c]--
l++
}
}
if k < 0 {
return ""
}
return s[k : k+mi]
}use std::collections::HashMap;
impl Solution {
pub fn min_window(s: String, t: String) -> String {
let mut need: HashMap<char, usize> = HashMap::new();
let mut window: HashMap<char, usize> = HashMap::new();
for c in t.chars() {
*need.entry(c).or_insert(0) += 1;
}
let m = s.len();
let n = t.len();
let mut k = -1;
let mut mi = m + 1;
let mut cnt = 0;
let s_bytes = s.as_bytes();
let mut l = 0;
for r in 0..m {
let c = s_bytes[r] as char;
*window.entry(c).or_insert(0) += 1;
if window[&c] <= *need.get(&c).unwrap_or(&0) {
cnt += 1;
}
while cnt == n {
if r - l + 1 < mi {
mi = r - l + 1;
k = l as i32;
}
let c = s_bytes[l] as char;
if window[&c] <= *need.get(&c).unwrap_or(&0) {
cnt -= 1;
}
*window.entry(c).or_insert(0) -= 1;
l += 1;
}
}
if k < 0 {
return String::new();
}
s[k as usize..(k as usize + mi)].to_string()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Hashmap | Time Complexity: O(m + n) since every character in "s" and "t" is evaluated at most twice. |
| Generate All Substrings and Check Validity | Time Complexity: O(m^2 * n) from nested loop orders and count evaluations. |
| Counting + Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Generate All Substrings and Check Validity | O(n² * k) | O(k) | Good for understanding the problem or very small strings |
| Sliding Window with Hashmap | O(n) | O(k) | Optimal solution for large inputs and expected in coding interviews |
Frequently asked questions
Is Minimum Window Substring easy or hard?
Minimum Window Substring is classified as a Hard problem because managing the sliding window conditions correctly is tricky. Many candidates struggle with maintaining frequency counts and shrinking the window without breaking validity.
Minimum Window Substring Python/Java solution
Python and Java solutions typically implement the sliding window approach using a dictionary or HashMap for character counts. Two pointers track the current substring while counters track how many required characters are satisfied, ensuring the smallest valid window is found efficiently.
How to solve Minimum Window Substring in O(n)?
Use a sliding window with two pointers and a hashmap that stores required character counts from t. Move the right pointer to expand the window and include characters. When all required characters are present, move the left pointer to shrink the window and keep the substring minimal while updating the best answer.
What is the best approach for Minimum Window Substring?
The sliding window with a hashmap is the best approach. It tracks character frequencies from string t and expands or shrinks a window over string s to maintain a valid substring. Each character is processed at most twice, giving O(n) time complexity and O(k) space complexity where k is the number of unique characters in t.
Is Minimum Window Substring asked at Google/Amazon/Meta?
Minimum Window Substring frequently appears in interviews at companies like Google, Amazon, Meta, and Microsoft. It tests sliding window mastery, hashmap usage, and the ability to manage dynamic constraints in string problems.
What data structure is used in Minimum Window Substring?
The core data structure is a hashmap (or frequency array) that stores how many times each character from t must appear in the current window. Combined with two pointers, this structure enables constant-time updates while expanding or shrinking the substring window.
What is the time complexity of Minimum Window Substring?
The optimal sliding window solution runs in O(n) time where n is the length of string s. Each character is visited at most twice by the left and right pointers. The space complexity is O(k) for storing frequency counts of characters in t.