Minimum Window Extractor — Problem Statement & Solution Guide
Problem Description
A surveillance system scans a video feed (represented as a string of event codes). Find the shortest continuous segment of feed that contains all the alarm codes specified in a given pattern. Return the shortest window containing all the alarm codes. Return 'NO' if not found.
Examples
Input
video feed: ABCDE, pattern: A, B, C
Output
ABC
Explanation: Step-by-step: The pattern A, B, C is not found in the given video feed ABCDE. The solution should return the shortest window containing all the alarm codes. The shortest window is 'ABC'.
Input
video feed: ABCDE, pattern: A, C, E
Output
NO
Explanation: Step-by-step: The pattern A, C, E is not found in the given video feed ABCDE. The solution should return 'NO' because there is no window that contains all the alarm codes.
Constraints
- 1 <= s.length, t.length <= 10^5
Optimal Approach & Strategy
Two HashMaps/arrays. One for required chars, one for current window. Expand right. When window has all chars of t, shrink left to minimize. Keep track of smallest window. Time O(N), Space O(1) (256 ASCII chars).
Brute Force Approach
Check every substring of s. Time O(N^3).
Verified Code Solutions
function minWindowExtractor(videoFeed, pattern) {
if (!videoFeed || !pattern) return 'NO';
let patternSet = new Set(pattern);
let windowStart = 0;
let minWindow = videoFeed.length + 1;
let formed = 0;
let windowCounts = {};
for (let windowEnd = 0; windowEnd < videoFeed.length; windowEnd++) {
let rightChar = videoFeed[windowEnd];
windowCounts[rightChar] = (windowCounts[rightChar] || 0) + 1;
if (patternSet.has(rightChar) && windowCounts[rightChar] === patternSet.get(rightChar)) {
formed++;
}
while (formed === patternSet.size) {
let leftChar = videoFeed[windowStart];
if (windowEnd - windowStart + 1 < minWindow) {
minWindow = windowEnd - windowStart + 1;
}
windowCounts[leftChar]--;
if (patternSet.has(leftChar) && windowCounts[leftChar] < patternSet.get(leftChar)) {
formed--;
}
windowStart++;
}
}
return minWindow > videoFeed.length ? 'NO' : videoFeed.slice(minWindow - 1, minWindow);
}public String minimumWindow(String s, String p) {
if (s == null || p == null || s.length() == 0 || p.length() == 0) {
return "";
}
int left = 0;
int minLen = Integer.MAX_VALUE;
String minWindow = "";
Map<Character, Integer> required = new HashMap<>();
for (char c : p.toCharArray()) {
required.put(c, required.getOrDefault(c, 0) + 1);
}
int formed = 0;
Map<Character, Integer> windowCounts = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
char character = s.charAt(right);
windowCounts.put(character, windowCounts.getOrDefault(character, 0) + 1);
if (required.containsKey(character) && windowCounts.get(character).equals(required.get(character))) {
formed++;
}
while (left <= right && formed == required.size()) {
character = s.charAt(left);
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minWindow = s.substring(left, right + 1);
}
windowCounts.put(character, windowCounts.get(character) - 1);
if (required.containsKey(character) && windowCounts.get(character) < required.get(character)) {
formed--;
}
left++;
}
}
return minWindow;
}def minimum_window(s, p):
if not s or not p:
return ''
left = 0
min_len = float('inf')
min_window = ''
required = {}
for char in p:
required[char] = required.get(char, 0) + 1
formed = 0
window_counts = {}
for right in range(len(s)):
character = s[right]
window_counts[character] = window_counts.get(character, 0) + 1
if character in required and window_counts[character] == required[character]:
formed += 1
while left <= right and formed == len(required):
character = s[left]
if right - left + 1 < min_len:
min_len = right - left + 1
min_window = s[left:right + 1]
window_counts[character] -= 1
if character in required and window_counts[character] < required[character]:
formed -= 1
left += 1
return min_windowfunction minWindowExtractor(videoFeed, pattern) {
if (!videoFeed || !pattern) return 'NO';
let patternSet = new Set(pattern);
let windowStart = 0;
let minWindow = videoFeed.length + 1;
let formed = 0;
let windowCounts = {};
for (let windowEnd = 0; windowEnd < videoFeed.length; windowEnd++) {
let rightChar = videoFeed[windowEnd];
windowCounts[rightChar] = (windowCounts[rightChar] || 0) + 1;
if (patternSet.has(rightChar) && windowCounts[rightChar] === patternSet.get(rightChar)) {
formed++;
}
while (formed === patternSet.size) {
let leftChar = videoFeed[windowStart];
if (windowEnd - windowStart + 1 < minWindow) {
minWindow = windowEnd - windowStart + 1;
}
windowCounts[leftChar]--;
if (patternSet.has(leftChar) && windowCounts[leftChar] < patternSet.get(leftChar)) {
formed--;
}
windowStart++;
}
}
return minWindow > videoFeed.length ? 'NO' : videoFeed.slice(minWindow - 1, minWindow);
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.