Welcome to Subscribe On Youtube
76. Minimum Window Substring
Description
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.length
n == t.length
1 <= m, n <= 10^{5}
s
andt
consist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n)
time?
Solutions
Solution 1: Counting + Two Pointers
We use a hash table or array $need$ to count the number of occurrences of each character in string $t$, and another hash table or array $window$ to count the number of occurrences of each character in the sliding window. In addition, we define two pointers $j$ and $i$ to point to the left and right boundaries of the window, respectively. The variable $cnt$ represents how many characters in $t$ are already included in the window. The variables $k$ and $mi$ represent the starting position and length of the minimum covering substring, respectively.
We traverse the string $s$ from left to right. For the currently traversed character $s[i]$:
We add it to the window, i.e., $window[s[i]] = window[s[i]] + 1$. If $need[s[i]] \geq window[s[i]]$ at this time, it means that $s[i]$ is a “necessary character”, so we increment $cnt$ by one. If $cnt$ equals the length of $t$, it means that all characters in $t$ are already included in the window at this time, so we can try to update the starting position and length of the minimum covering substring. If $i  j + 1 \lt mi$, it means that the substring represented by the current window is shorter, so we update $mi = i  j + 1$ and $k = j$. Then, we try to move the left boundary $j$. If $need[s[j]] \geq window[s[j]]$ at this time, it means that $s[j]$ is a “necessary character”. When moving the left boundary, the character $s[j]$ will be removed from the window, so we need to decrement $cnt$ by one, then update $window[s[j]] = window[s[j]]  1$, and move $j$ one step to the right. If $cnt$ does not equal the length of $t$, it means that all characters in $t$ are not yet included in the window at this time, so we don’t need to move the left boundary, just move $i$ one step to the right and continue to traverse.
After the traversal, if the minimum covering substring is not found, return an empty string, otherwise return $s[k:k+mi]$.
The time complexity is $O(m + n)$, and the space complexity is $O(C)$. Here, $m$ and $n$ are the lengths of strings $s$ and $t$ respectively; and $C$ is the size of the character set, in this problem $C = 128$.
why <=
is used instead of <
in the condition if d[c] <= need[c]: cnt += 1
?
Let’s consider an example to illustrate why <=
is used instead of <
in the condition if d[c] <= need[c]: cnt += 1
.
Suppose we have:
s = "ABAACBAB"
t = "ABC"
We want to find the minimum window in s
that contains all the characters in t
.
StepbyStep Process:
 Initialization:
need = {'A': 1, 'B': 1, 'C': 1}
(The count of each character needed fromt
.)d = {}
(To keep track of characters in the current window.)cnt = 0
(To count how many of the required characters we have in the current window.)
 First Window:
 We traverse
s
and encounterA
.d = {'A': 1}
.  Since
d['A'] (1) <= need['A'] (1)
, we incrementcnt
to1
.  We continue and encounter another
A
. Now,d = {'A': 2}
.  Now,
d['A'] (2) > need['A'] (1)
, so we don’t incrementcnt
. We have moreA
s than needed for a valid window.
 We traverse
 Continuing:
 The next character is
B
.d = {'A': 2, 'B': 1}
. d['B'] (1) <= need['B'] (1)
, so we incrementcnt
to2
. Then, we encounter
A
again,d = {'A': 3, 'B': 1}
, still no increment tocnt
because we already have moreA
s than required.  Next is
C
.d = {'A': 3, 'B': 1, 'C': 1}
. d['C'] (1) <= need['C'] (1)
, incrementcnt
to3
.
 The next character is
 Valid Window Found:
 At this point,
cnt == len(t)
, meaning we have a valid window that contains at least as many of each required character as int
.  If we used
<
instead of<=
, we wouldn’t have counted the first occurrence of each character towardscnt
when it exactly matched the requirement, potentially missing the earliest valid window.
 At this point,
 Shrinking the Window:
 As we continue to traverse and adjust our window, we aim to minimize it while maintaining
cnt == len(t)
.  The condition
d[c] <= need[c]
correctly incrementscnt
for characters that meet the requirement exactly, crucial for identifying the minimum window.
 As we continue to traverse and adjust our window, we aim to minimize it while maintaining
In this example, using <=
allows us to correctly increment cnt
when a character occurrence transitions from not meeting to meeting the exact requirement. It ensures we recognize when we first have a valid window ("ABAAC"
), allowing us to then attempt to minimize it while still covering all characters in t
. The use of <
would delay recognizing a valid window until we had more characters than necessary, potentially missing the minimum valid window.

class Solution { public String minWindow(String s, String t) { int[] need = new int[128]; int[] window = new int[128]; int m = s.length(), n = t.length(); for (int i = 0; i < n; ++i) { ++need[t.charAt(i)]; } int cnt = 0, j = 0, k = 1, mi = 1 << 30; for (int i = 0; i < m; ++i) { ++window[s.charAt(i)]; if (need[s.charAt(i)] >= window[s.charAt(i)]) { ++cnt; } while (cnt == n) { if (i  j + 1 < mi) { mi = i  j + 1; k = j; } if (need[s.charAt(j)] >= window[s.charAt(j)]) { cnt; } window[s.charAt(j++)]; } } return k < 0 ? "" : s.substring(k, k + mi); } }

class Solution { public: string minWindow(string s, string t) { int need[128]{}; int window[128]{}; int m = s.size(), n = t.size(); for (char& c : t) { ++need[c]; } int cnt = 0, j = 0, k = 1, mi = 1 << 30; for (int i = 0; i < m; ++i) { ++window[s[i]]; if (need[s[i]] >= window[s[i]]) { ++cnt; } while (cnt == n) { if (i  j + 1 < mi) { mi = i  j + 1; k = j; } if (need[s[j]] >= window[s[j]]) { cnt; } window[s[j++]]; } } return k < 0 ? "" : s.substr(k, mi); } };

''' >>> deq = collections.deque([]) >>> deq.append(11) >>> deq.append(22) >>> deq.append(33) >>> >>> deq[0] 11 ''' import collections class Solution: def minWindow(self, s: str, t: str) > str: cnt = 0 need = collections.Counter(t) start, end = len(s), 3 * len(s) # Arbitrary 3, just make sure endstart is larger than input s length, for later mincheck d = {} # Using queue to store indexes, good for a large amount of API calls deq = collections.deque([]) for i, c in enumerate(s): if c in need: deq.append(i) d[c] = d.get(c, 0) + 1 # '=' also +1, because it's inceased already one line above :) if d[c] <= need[c]: cnt += 1 while deq and d[s[deq[0]]] > need[s[deq[0]]]: d[s[deq.popleft()]] = 1 if cnt == len(t) and deq[1]  deq[0] < end  start: start, end = deq[0], deq[1] return s[start:end + 1] ############ from collections import Counter class Solution: def minWindow(self, s: str, t: str) > str: ans = '' m, n = len(s), len(t) if m < n: return ans need = Counter(t) window = Counter() i, cnt, mi = 0, 0, inf for j, c in enumerate(s): window[c] += 1 if need[c] >= window[c]: # >= , because 1 line above already +=1 cnt += 1 while cnt == n: if j  i + 1 < mi: # in while mi = j  i + 1 ans = s[i : j + 1] c = s[i] if need[c] >= window[c]: # char in window but not in need, need[c]=0, window[c]=1..2.. cnt = 1 window[c] = 1 i += 1 return ans

func minWindow(s string, t string) string { need := [128]int{} window := [128]int{} for _, c := range t { need[c]++ } cnt, j, k, mi := 0, 0, 1, 1<<30 for i, c := range s { window[c]++ if need[c] >= window[c] { cnt++ } for cnt == len(t) { if ij+1 < mi { mi = i  j + 1 k = j } if need[s[j]] >= window[s[j]] { cnt } window[s[j]] j++ } } if k < 0 { return "" } return s[k : k+mi] }

function minWindow(s: string, t: string): string { const need: number[] = new Array(128).fill(0); const window: number[] = new Array(128).fill(0); for (const c of t) { ++need[c.charCodeAt(0)]; } let cnt = 0; let j = 0; let k = 1; let mi = 1 << 30; for (let i = 0; i < s.length; ++i) { ++window[s.charCodeAt(i)]; if (need[s.charCodeAt(i)] >= window[s.charCodeAt(i)]) { ++cnt; } while (cnt === t.length) { if (i  j + 1 < mi) { mi = i  j + 1; k = j; } if (need[s.charCodeAt(j)] >= window[s.charCodeAt(j)]) { cnt; } window[s.charCodeAt(j++)]; } } return k < 0 ? '' : s.slice(k, k + mi); }

public class Solution { public string MinWindow(string s, string t) { int[] need = new int[128]; int[] window = new int[128]; foreach (var c in t) { ++need[c]; } int cnt = 0, j = 0, k = 1, mi = 1 << 30; for (int i = 0; i < s.Length; ++i) { ++window[s[i]]; if (need[s[i]] >= window[s[i]]) { ++cnt; } while (cnt == t.Length) { if (i  j + 1 < mi) { mi = i  j + 1; k = j; } if (need[s[j]] >= window[s[j]]) { cnt; } window[s[j++]]; } } return k < 0 ? "" : s.Substring(k, mi); } }

impl Solution { pub fn min_window(s: String, t: String) > String { let (mut need, mut window, mut cnt) = ([0; 256], [0; 256], 0); for c in t.chars() { need[c as usize] += 1; } let (mut j, mut k, mut mi) = (0, 1, 1 << 31); for (i, c) in s.chars().enumerate() { window[c as usize] += 1; if need[c as usize] >= window[c as usize] { cnt += 1; } while cnt == t.len() { if i  j + 1 < mi { k = j as i32; mi = i  j + 1; } let l = s.chars().nth(j).unwrap() as usize; if need[l] >= window[l] { cnt = 1; } window[l] = 1; j += 1; } } if k < 0 { return "".to_string(); } let k = k as usize; s[k..k + mi].to_string() } }