Minimum Window Substring
A monitoring tool records events as a string s, one letter per event, where uppercase and lowercase letters are different event types. An engineer wants the shortest stretch of the log that contains every event listed in t, counting repeats: if t lists an event type twice, the stretch must contain it at least twice.
Return that shortest contiguous stretch of s. If no stretch qualifies, return the empty string "". Whenever an answer exists, the tests make sure the shortest stretch is unique.
Input: s = "ZAQBXCBAY", t = "ABC" Output: "CBA"
Explanation: "AQBXC" also contains A, B and C, but the three-letter stretch "CBA" is shorter.
Input: s = "baacab", t = "aab" Output: "baa"
Explanation: t needs two as and one b. "baa" is the only three-letter stretch that has them all.
Input: s = "Abc", t = "a" Output: ""
Explanation: Event types are case-sensitive: s contains A but no a.
Constraints
sandtare each between 1 and 10^5 characters long.- Both strings contain only English letters, uppercase or lowercase.
Follow-up: Checking every start and end position is easy but slow. Can you get the running time down to one pass over s plus one pass over t?
💡 Hint 1
Count what t needs. A window of s is valid when it has at least that many of every character.
💡 Hint 2
Grow a window to the right until it is valid, then shrink it from the left for as long as it stays valid, recording the shortest valid window.
💡 Hint 3
Track a single number, how many required characters are still missing, so validity is an O(1) check instead of comparing all counts.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Use a sliding window with a table need of how many more of each character the window requires, and a counter missing of required characters not yet covered (initially t.length). Move right across s: if need[c] > 0 the new character fills a gap, so decrement missing; decrement need[c] either way (it goes negative for surplus). Whenever missing == 0 the window is valid: record it if it is the shortest so far, then remove s[left] (increment its need; if that becomes positive a required character is now missing) and advance left. Each index enters and leaves the window once.
function minWindow(s, t) {
const need = new Array(128).fill(0);
for (let i = 0; i < t.length; i++) need[t.charCodeAt(i)]++;
let missing = t.length;
let bestStart = 0;
let bestLen = Infinity;
let left = 0;
for (let right = 0; right < s.length; right++) {
const c = s.charCodeAt(right);
if (need[c] > 0) missing--;
need[c]--;
while (missing === 0) {
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
const d = s.charCodeAt(left);
need[d]++;
if (need[d] > 0) missing++;
left++;
}
}
return bestLen === Infinity ? '' : s.slice(bestStart, bestStart + bestLen);
}class Solution {
public String minWindow(String s, String t) {
int[] need = new int[128];
for (int i = 0; i < t.length(); i++) need[t.charAt(i)]++;
int missing = t.length(), bestStart = 0, bestLen = Integer.MAX_VALUE, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (need[c] > 0) missing--;
need[c]--;
while (missing == 0) {
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestStart = left;
}
char d = s.charAt(left);
need[d]++;
if (need[d] > 0) missing++;
left++;
}
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
function minWindow(s, t) {
}Run your code to see results here.