Practice › Sliding Window
Minimum Window Substring
Hard · Sliding Window · Asked at Meta, Amazon, Google, Microsoft, Uber
Find the shortest substring of s that contains every character of t, including duplicates. If several windows have the minimum length, print the leftmost one. If no window exists, print -1.
Input
First line: s. Second line: t. Both consist of English letters (upper and lower case).
Output
The minimum window, or -1.
Constraints
- 1 ≤ |s|, |t| ≤ 10^5
Expand the right end until the window covers t, then shrink from the left as long as it still covers t. Track how many required characters are still missing.
Example 1
Input
ADOBECODEBANC ABC
Output
BANC
Example 2
Input
a aa
Output
-1
Hints
- Count what t needs. Expand the right end of the window, and track how many required characters are still missing.
- When nothing is missing, the window is valid: record it if it is shorter, then shrink from the left while it stays valid.
Approach
need[c] = occurrences of c in t; missing = |t|. Move r over s: increment have[s[r]], and if that character was still needed (have ≤ need), decrement missing. While missing == 0, the window [l, r] covers t — update the answer (only when strictly shorter, so the leftmost window wins ties), then remove s[l], and if that makes a needed count drop below need, increment missing; advance l. Each index enters and leaves once.
Complexity: O(|s| + |t|) time · O(alphabet) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, t;
cin >> s >> t;
vector<int> need(128, 0), have(128, 0);
for (char c : t) need[c]++;
int missing = t.size(), l = 0, bestL = -1, bestLen = INT_MAX;
for (int r = 0; r < (int)s.size(); r++) {
if (++have[s[r]] <= need[s[r]]) missing--;
while (missing == 0) {
if (r - l + 1 < bestLen) bestLen = r - l + 1, bestL = l;
if (--have[s[l]] < need[s[l]]) missing++;
l++;
}
}
if (bestL < 0) cout << -1 << "\n";
else cout << s.substr(bestL, bestLen) << "\n";
return 0;
}Python solution
import sys
s, t = sys.stdin.read().split()[:2]
need, have = [0] * 128, [0] * 128
for c in t:
need[ord(c)] += 1
missing, l, best = len(t), 0, None
for r, c in enumerate(s):
have[ord(c)] += 1
if have[ord(c)] <= need[ord(c)]:
missing -= 1
while missing == 0:
if best is None or r - l + 1 < best[1] - best[0]:
best = (l, r + 1)
d = ord(s[l])
have[d] -= 1
if have[d] < need[d]:
missing += 1
l += 1
print(s[best[0] : best[1]] if best else -1)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next(), t = sc.next();
int[] need = new int[128], have = new int[128];
for (char c : t.toCharArray()) need[c]++;
int missing = t.length(), l = 0, bestL = -1, bestLen = Integer.MAX_VALUE;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
if (++have[c] <= need[c]) missing--;
while (missing == 0) {
if (r - l + 1 < bestLen) {
bestLen = r - l + 1;
bestL = l;
}
char d = s.charAt(l++);
if (--have[d] < need[d]) missing++;
}
}
System.out.println(bestL < 0 ? "-1" : s.substring(bestL, bestL + bestLen));
}
}Solve Minimum Window Substring online · All practice problems