Minimum Window Extractor — Problem Statement & Solution Guide

Sliding WindowHardSliding Window / Hash Map

TimeO(|S| + |P|)

SpaceO(K)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Sliding Window and solve the Minimum Window Extractor problem optimally.

TopicSliding Window

PatternSliding Window / Hash Map

TimeO(|S| + |P|)

SpaceO(K)

Problem Description

A surveillance system receives a continuous stream of event codes represented as a string S. A separate string P lists the alarm codes that must all appear in a segment of the stream. Your task is to find the shortest contiguous substring of S that contains every character of P at least once. If no such substring exists, return the string "NO". The solution must be efficient enough to handle streams of up to 10^5 characters.

DSA Pattern Breakdown

"Minimum Window Extractor"

hard

WHY DOES IT MATTER?

The sliding‑window pattern transforms problems that appear to require exhaustive enumeration into linear‑time solutions by exploiting the monotonic nature of the constraint. Recognizing when a problem can be expressed as "find the smallest/largest subarray satisfying a condition" unlocks a powerful tool that appears in cache eviction policies, network packet inspection, and real‑time analytics.

OPTIMIZATION CHALLENGE

The key insight is that each pointer moves only forward; therefore, each character of S is added to and removed from the window at most once. By coupling this with a frequency deficit counter that tells us in O(1) whether the current window satisfies P, we avoid re‑scanning the window for every new right‑hand expansion, collapsing the naive quadratic bound to linear.

REAL-WORLD CONNECTION

Imagine a network intrusion detection system that must raise an alert as soon as a burst of suspicious packets (represented by characters) appears within a sliding time frame. The system continuously slides a time window over the packet stream, expanding when new packets arrive and contracting when old packets fall out, exactly mirroring the minimum window extractor logic.

During an interview, start by writing the frequency map for P, then implement two pointers with a while‑loop that expands right until the window is valid, followed by an inner loop that contracts left while still valid. Keep track of the best window length and its indices; this structure makes the code easy to reason about and debug.

COMPLEXITY AT A GLANCE

⏱ Time:O(|S| + |P|)

💾 Space:O(K)

Core Theory — Why This Approach?

The Minimum Window Substring problem is a classic example of the sliding‑window technique combined with a frequency‑map. The goal is to maintain a dynamic interval [left, right] over the source string S such that the interval always contains all characters of the pattern P with at least the required multiplicities. A naive solution would enumerate every possible start index and expand to the right until the window satisfies the requirement, leading to O(|S|·|S|) time, which is infeasible for large streams (|S| can be up to 10^5 or more). By using two pointers that only move forward, we can shrink the left side as soon as the window is valid, guaranteeing each character is visited at most twice – once when the right pointer includes it and once when the left pointer excludes it. The frequency map (often an array of size 256 for ASCII or a hashmap for Unicode) tracks the deficit of each needed character, allowing O(1) checks for window validity. This paradigm—expanding to satisfy a constraint then contracting to improve optimality—is the essence of many "minimum window" and "longest substring with at most K distinct" problems, making it a cornerstone of efficient string processing.

Interview Questions on This Problem

Q1How would you modify the sliding‑window solution if the pattern P can contain duplicate characters (e.g., P = "AAB")?

Maintain a count map for P that records the required frequency of each character. While expanding the window, decrement the map only when the character is needed and its count is still positive. Track a variable "formed" that increments when a character’s count reaches zero. The window is valid only when "formed" equals the number of unique characters in P. This handles duplicates without extra complexity.

Q2What is the time complexity of the algorithm if the input strings consist of Unicode characters beyond the ASCII range?

The algorithm remains O(|S| + |P|) because each character is processed a constant number of times; however, using a hashmap for the frequency map introduces an O(1) average‑case lookup cost, keeping the overall complexity linear in the length of the strings.

Q3Can the minimum window problem be solved in a single pass without storing the entire frequency map of P? Explain a scenario where this is possible.

If P contains only distinct characters, you can use a bitmask (or an integer array of size 26 for lowercase letters) to represent required characters, eliminating the need for a full hashmap. The algorithm still follows the expand‑shrink pattern, but the validity check becomes a simple bitwise comparison, allowing a true single‑pass solution with O(1) auxiliary space.

Examples

Example 1

Input

S=ADOBECODEBANC
P=ABC

Output

BANC

Explanation: The window "BANC" (indices 9–12) contains A, B, and C and is the shortest possible. Any smaller window fails to include all three characters.

Example 2

Input

S=AAABBBCCC
P=ABC

Output

ABBC

Explanation: The minimal window starts at the last A (index 2) and ends at the first C (index 6), yielding "ABBC" of length 4. No shorter window contains A, B, and C.

Example 3

Input

S=XYZ
P=ABC

Output

NO

Explanation: None of the characters A, B, or C appear in S, so a valid window cannot be formed.

Example 4

Input

S=aabcbcdbca
P=abc

Output

bca

Explanation: The substring "bca" (indices 7–9) contains a, b, and c and has length 3, which is minimal.

Constraints

1 <= |S| <= 100000
1 <= |P| <= 10000
S and P consist of printable ASCII characters
Time complexity must be O(|S| + |P|)

Optimal Approach & Strategy

Use a sliding window with a frequency map; expand the right pointer until the window is valid, then contract the left pointer while maintaining validity, updating the best window – achieving linear time.

Brute Force Approach

Enumerate every possible start index, expand to the right until the substring contains all characters of P, record the length, and keep the minimum; this results in O(|S|^2) time.

Code Solutions

Language:

JavaScript Solution

Time: O(|S| + |P|)

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    if (s.length === 0 || t.length === 0 || s.length < t.length) return "";
    
    const tCount = new Map();
    for (let c of t) {
        tCount.set(c, (tCount.get(c) || 0) + 1);
    }
    
    const required = tCount.size;
    let formed = 0;
    const windowCount = new Map();
    
    let left = 0;
    let ansLength = Infinity;
    let ansLeft = 0;
    let ansRight = 0;
    
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        windowCount.set(c, (windowCount.get(c) || 0) + 1);
        
        if (tCount.has(c) && windowCount.get(c) === tCount.get(c)) {
            formed++;
        }
        
        while (formed === required) {
            if (right - left + 1 < ansLength) {
                ansLength = right - left + 1;
                ansLeft = left;
                ansRight = right;
            }
            
            const leftChar = s[left];
            windowCount.set(leftChar, windowCount.get(leftChar) - 1);
            if (tCount.has(leftChar) && windowCount.get(leftChar) < tCount.get(leftChar)) {
                formed--;
            }
            left++;
        }
    }
    
    if (ansLength === Infinity) return "";
    return s.substring(ansLeft, ansLeft + ansLength);
};

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.empty() || t.empty() || s.size() < t.size()) return "";
        
        unordered_map<char, int> tCount;
        for (char c : t) {
            tCount[c]++;
        }
        
        int required = tCount.size();
        int formed = 0;
        unordered_map<char, int> windowCount;
        
        int left = 0;
        int ansLength = INT_MAX;
        int ansLeft = 0;
        int ansRight = 0;
        
        for (int right = 0; right < s.size(); right++) {
            char c = s[right];
            windowCount[c]++;
            
            if (tCount.count(c) && windowCount[c] == tCount[c]) {
                formed++;
            }
            
            while (formed == required) {
                if (right - left + 1 < ansLength) {
                    ansLength = right - left + 1;
                    ansLeft = left;
                    ansRight = right;
                }
                
                char leftChar = s[left];
                windowCount[leftChar]--;
                if (tCount.count(leftChar) && windowCount[leftChar] < tCount[leftChar]) {
                    formed--;
                }
                left++;
            }
        }
        
        if (ansLength == INT_MAX) return "";
        return s.substr(ansLeft, ansLength);
    }
};

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) return "";
        
        Map<Character, Integer> tCount = new HashMap<>();
        for (char c : t.toCharArray()) {
            tCount.put(c, tCount.getOrDefault(c, 0) + 1);
        }
        
        int required = tCount.size();
        int formed = 0;
        Map<Character, Integer> windowCount = new HashMap<>();
        
        int left = 0;
        int ansLength = Integer.MAX_VALUE;
        int ansLeft = 0;
        int ansRight = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
            
            if (tCount.containsKey(c) && windowCount.get(c).equals(tCount.get(c))) {
                formed++;
            }
            
            while (formed == required) {
                if (right - left + 1 < ansLength) {
                    ansLength = right - left + 1;
                    ansLeft = left;
                    ansRight = right;
                }
                
                char leftChar = s.charAt(left);
                windowCount.put(leftChar, windowCount.get(leftChar) - 1);
                if (tCount.containsKey(leftChar) && windowCount.get(leftChar) < tCount.get(leftChar)) {
                    formed--;
                }
                left++;
            }
        }
        
        if (ansLength == Integer.MAX_VALUE) return "";
        return s.substring(ansLeft, ansLeft + ansLength);
    }
}

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t or len(s) < len(t):
            return ""
        
        from collections import Counter
        t_count = Counter(t)
        required = len(t_count)
        formed = 0
        window_count = {}
        
        left = 0
        ans_length = float('inf')
        ans_left = 0
        ans_right = 0
        
        for right in range(len(s)):
            c = s[right]
            window_count[c] = window_count.get(c, 0) + 1
            
            if c in t_count and window_count[c] == t_count[c]:
                formed += 1
            
            while formed == required:
                if right - left + 1 < ans_length:
                    ans_length = right - left + 1
                    ans_left = left
                    ans_right = right
                
                left_char = s[left]
                window_count[left_char] -= 1
                if left_char in t_count and window_count[left_char] < t_count[left_char]:
                    formed -= 1
                left += 1
        
        if ans_length == float('inf'):
            return ""
        return s[ans_left:ans_left + ans_length]

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    if (s.length === 0 || t.length === 0 || s.length < t.length) return "";
    
    const tCount = new Map();
    for (let c of t) {
        tCount.set(c, (tCount.get(c) || 0) + 1);
    }
    
    const required = tCount.size;
    let formed = 0;
    const windowCount = new Map();
    
    let left = 0;
    let ansLength = Infinity;
    let ansLeft = 0;
    let ansRight = 0;
    
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        windowCount.set(c, (windowCount.get(c) || 0) + 1);
        
        if (tCount.has(c) && windowCount.get(c) === tCount.get(c)) {
            formed++;
        }
        
        while (formed === required) {
            if (right - left + 1 < ansLength) {
                ansLength = right - left + 1;
                ansLeft = left;
                ansRight = right;
            }
            
            const leftChar = s[left];
            windowCount.set(leftChar, windowCount.get(leftChar) - 1);
            if (tCount.has(leftChar) && windowCount.get(leftChar) < tCount.get(leftChar)) {
                formed--;
            }
            left++;
        }
    }
    
    if (ansLength === Infinity) return "";
    return s.substring(ansLeft, ansLeft + ansLength);
};

Asked in Top Tech Interviews

Netflix

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.