Minimum Window Substring
Find the shortest substring of s containing every character of t with at least its frequency in t. If several shortest windows exist, use the earliest.
Work through the cases
3 examplesInput notation
s on line 1; nonempty t on line 2. Characters are case-sensitive.Expected result
The substring, or none.Case 1
Input
cabefgecdaecf cae
Expected output
aec
Case 2
Input
abc z
Expected output
none
Case 3
Input
aa aa
Expected output
aa
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Enumerate every substring of s and test coverage of t: O(m^2) windows, m ≤ 10^5 will TLE. The follow-up wants O(m+n). Once a window covers, extra characters on the left can go; if it does not cover, only the right end can grow. need stores t's quota, window stores the window, and cnt counts how many required occurrences are met, so coverage is O(1). Scan s with the right pointer; while valid, shrink the left and record the shortest span.
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. If need[s[r]] ≥ window[s[r]], it means s[r] is a "necessary character", and we increment cnt by one. - If cnt equals the length of t, it means the window already contains all characters from t, and we can try to update the starting position and length of the minimum window substring. If r - l + 1 < mi, it means the current window represents a shorter substring, so we update mi = r - l + 1 and k = l. - Then, we try to move the left boundary l. If need[s[l]] ≥ window[s[l]], it means s[l] is a "necessary character", and moving the left boundary will remove s[l] from the window. Therefore, we need to decrement cnt by one, update window[s[l]] = window[s[l]] - 1, and move l one position to the right. - If cnt is not equal to the length of t, it means the window does not yet contain all characters from t, so we do not need to move the left boundary. Instead, we move r one 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.
class Solution {
public String minWindow(String s, String t) {
int[] need = new int[128];
int[] window = new int[128];
for (char c : t.toCharArray()) {
++need[c];
}
int m = s.length(), n = t.length();
int k = -1, mi = m + 1, cnt = 0;
for (int l = 0, r = 0; r < m; ++r) {
char c = s.charAt(r);
if (++window[c] <= need[c]) {
++cnt;
}
while (cnt == n) {
if (r - l + 1 < mi) {
mi = r - l + 1;
k = l;
}
c = s.charAt(l);
if (window[c] <= need[c]) {
--cnt;
}
--window[c];
++l;
}
}
return k < 0 ? "" : s.substring(k, k + mi);
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.