What happens if you not handling characters in s that are not in t?

Unnecessary shrinking or expansion, inefficient code Fix: Only update 'have' counter and check validity for characters present in t

What happens if you returning the substring using wrong indices after the loop?

Off-by-one errors or empty string returned incorrectly Fix: Store start and end indices carefully and return substring accordingly

Interview Prepchallenge-problemshardAmazonFacebookGoogleMicrosoftLinkedIn

Minimum Window Substring

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

hardMIXEDAmazonFacebookGoogle

Imagine you are searching through a large document to find the shortest snippet that contains all the keywords you need for your research.

💡 This problem requires finding a substring that contains all characters of another string, which is tricky because beginners often struggle with efficiently tracking character frequencies and managing dynamic window sizes.

📋

Problem Statement

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

1 ≤ s.length, t.length ≤ 10^5s and t consist of English letters.

💡

Example

Input"s = \"ADOBECODEBANC\", t = \"ABC\""

Output"BANC"

The substring "BANC" contains all characters A, B, and C and is the shortest such substring.

t is longer than s → ""
s and t are identical → s
t contains characters not in s → ""
s or t is empty → ""

⚠️

Common Mistakes

Not checking if the window contains all required characters before shrinking

Returns incorrect or empty substring

✅ Use a 'have' counter to track when all required characters are included before shrinking

Using hash maps but forgetting to decrement counts when moving left pointer

Window counts become inaccurate, leading to incorrect results

✅ Always decrement the count of the character being removed from the window

Not handling characters in s that are not in t

Unnecessary shrinking or expansion, inefficient code

✅ Only update 'have' counter and check validity for characters present in t

Returning the substring using wrong indices after the loop

Off-by-one errors or empty string returned incorrectly

✅ Store start and end indices carefully and return substring accordingly

Using nested loops in brute force without pruning

Code times out on large inputs

✅ Explain brute force only conceptually and move to sliding window for coding

🧠

Brute Force (Nested Loops Checking All Substrings)

💡 Starting with brute force helps understand the problem deeply by checking every possible substring, even though it's inefficient.

Intuition

Check every substring of s and verify if it contains all characters of t by counting frequencies.

Algorithm

Generate all possible substrings of s.
For each substring, count the frequency of characters.
Check if the substring contains all characters of t with required frequency.
Keep track of the minimum length substring that satisfies the condition.

💡 The nested loops and frequency checks make this approach easy to understand but hard to optimize without further insight.

</>

Code

def min_window_brute_force(s: str, t: str) -> str:
    from collections import Counter
    if not s or not t:
        return ""
    t_count = Counter(t)
    required = len(t_count)
    min_len = float('inf')
    min_window = ""
    for i in range(len(s)):
        for j in range(i, len(s)):
            window = s[i:j+1]
            window_count = Counter(window)
            if all(window_count[c] >= t_count[c] for c in t_count):
                if j - i + 1 < min_len:
                    min_len = j - i + 1
                    min_window = window
    return min_window

# Example usage:
if __name__ == "__main__":
    print(min_window_brute_force("ADOBECODEBANC", "ABC"))  # Output: BANC

Line Notes

from collections import CounterImport Counter to easily count character frequencies, which simplifies frequency comparisons.

if not s or not t:Handle edge cases where input strings are empty to avoid unnecessary computation.

for i in range(len(s))Outer loop selects the start index of the substring to consider.

for j in range(i, len(s))Inner loop selects the end index of the substring, generating all substrings.

window_count = Counter(window)Count characters in the current substring to compare with required frequencies.

if all(window_count[c] >= t_count[c] for c in t_count)Check if current substring contains all required characters with correct frequency.

if j - i + 1 < min_lenUpdate minimum window if current substring is smaller than previously found ones.

import java.util.*;
public class MinWindowSubstringBrute {
    public static String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) return "";
        Map<Character, Integer> tCount = new HashMap<>();
        for (char c : t.toCharArray()) tCount.put(c, tCount.getOrDefault(c, 0) + 1);
        int minLen = Integer.MAX_VALUE;
        String minWindow = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String window = s.substring(i, j + 1);
                Map<Character, Integer> windowCount = new HashMap<>();
                for (char c : window.toCharArray()) windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
                boolean valid = true;
                for (char c : tCount.keySet()) {
                    if (windowCount.getOrDefault(c, 0) < tCount.get(c)) {
                        valid = false;
                        break;
                    }
                }
                if (valid && window.length() < minLen) {
                    minLen = window.length();
                    minWindow = window;
                }
            }
        }
        return minWindow;
    }
    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC")); // Output: BANC
    }
}

Line Notes

if (s == null || t == null || s.length() == 0 || t.length() == 0)Check for empty or null inputs early to avoid unnecessary processing.

for (char c : t.toCharArray())Count frequency of characters in t to know requirements.

for (int i = 0; i < s.length(); i++)Outer loop selects start index of substring.

for (int j = i; j < s.length(); j++)Inner loop selects end index of substring.

Map<Character, Integer> windowCount = new HashMap<>();Count characters in current substring for frequency comparison.

if (windowCount.getOrDefault(c, 0) < tCount.get(c))Check if current substring lacks required characters.

if (valid && window.length() < minLen)Update minimum window if current substring is valid and smaller.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

string minWindowBrute(string s, string t) {
    if (s.empty() || t.empty()) return "";
    unordered_map<char, int> tCount;
    for (char c : t) tCount[c]++;
    int minLen = INT_MAX;
    string minWindow = "";
    for (int i = 0; i < (int)s.size(); i++) {
        for (int j = i; j < (int)s.size(); j++) {
            unordered_map<char, int> windowCount;
            for (int k = i; k <= j; k++) windowCount[s[k]]++;
            bool valid = true;
            for (auto &p : tCount) {
                if (windowCount[p.first] < p.second) {
                    valid = false;
                    break;
                }
            }
            if (valid && j - i + 1 < minLen) {
                minLen = j - i + 1;
                minWindow = s.substr(i, minLen);
            }
        }
    }
    return minWindow;
}

int main() {
    cout << minWindowBrute("ADOBECODEBANC", "ABC") << endl; // Output: BANC
    return 0;
}

Line Notes

if (s.empty() || t.empty()) return "";Handle empty input strings immediately to avoid unnecessary computation.

for (char c : t) tCount[c]++;Count frequency of characters in t to know requirements.

for (int i = 0; i < (int)s.size(); i++)Outer loop selects start index of substring.

for (int j = i; j < (int)s.size(); j++)Inner loop selects end index of substring.

for (int k = i; k <= j; k++) windowCount[s[k]]++;Count characters in current substring for frequency comparison.

if (windowCount[p.first] < p.second)Check if current substring lacks required characters.

if (valid && j - i + 1 < minLen)Update minimum window if current substring is valid and smaller.

function minWindowBruteForce(s, t) {
    if (!s || !t) return "";
    const tCount = {};
    for (const c of t) tCount[c] = (tCount[c] || 0) + 1;
    let minLen = Infinity;
    let minWindow = "";
    for (let i = 0; i < s.length; i++) {
        for (let j = i; j < s.length; j++) {
            const window = s.substring(i, j + 1);
            const windowCount = {};
            for (const c of window) windowCount[c] = (windowCount[c] || 0) + 1;
            let valid = true;
            for (const c in tCount) {
                if (!windowCount[c] || windowCount[c] < tCount[c]) {
                    valid = false;
                    break;
                }
            }
            if (valid && window.length < minLen) {
                minLen = window.length;
                minWindow = window;
            }
        }
    }
    return minWindow;
}

// Example usage:
console.log(minWindowBruteForce("ADOBECODEBANC", "ABC")); // Output: BANC

Line Notes

if (!s || !t) return "";Return empty string if inputs are empty or null to handle edge cases.

for (const c of t) tCount[c] = (tCount[c] || 0) + 1;Count frequency of characters in t to know requirements.

for (let i = 0; i < s.length; i++)Outer loop selects start index of substring.

for (let j = i; j < s.length; j++)Inner loop selects end index of substring.

for (const c of window) windowCount[c] = (windowCount[c] || 0) + 1;Count characters in current substring for frequency comparison.

if (!windowCount[c] || windowCount[c] < tCount[c])Check if current substring lacks required characters.

if (valid && window.length < minLen)Update minimum window if current substring is valid and smaller.

⏱

Complexity

TimeO(n^3)

SpaceO(n)

There are O(n^2) substrings and counting frequencies for each substring takes O(n), resulting in O(n^3) time.

💡 For n=20, this means roughly 8000 operations, which is slow but manageable; for n=1000, it becomes impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n^3)`	`O(n)`	No	N/A	Mention only - never code
2. Sliding Window with Hash Maps	`O(n)`	`O(m)`	No	Yes	Code this approach in most interviews
3. Optimized Sliding Window with Arrays	`O(n)`	`O(1)`	No	Yes	Mention as optimization if input is ASCII

Practice

(1/5)

1. Given an integer array and an integer k, you need to count the number of contiguous subarrays that contain exactly k odd numbers. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force nested loops checking all subarrays and counting odd numbers

B. Dynamic programming with state representing counts of odd numbers in subarrays

C. Sliding window with two pointers maintaining at most k odd numbers and using inclusion-exclusion

D. Greedy approach expanding subarrays until k odd numbers are found, then restarting

2. Given the following code for maxSatisfied, what is the value of max_extra after the first for-loop that slides the window (before the final return) when called with customers = [1, 0, 1, 2], grumpy = [1, 0, 1, 1], and X = 2?

def maxSatisfied(customers, grumpy, X):
    n = len(customers)
    base_satisfied = 0
    for i in range(n):
        if grumpy[i] == 0:
            base_satisfied += customers[i]
    window_sum = 0
    for i in range(X):
        if grumpy[i] == 1:
            window_sum += customers[i]
    max_extra = window_sum
    for i in range(X, n):
        if grumpy[i] == 1:
            window_sum += customers[i]
        if grumpy[i - X] == 1:
            window_sum -= customers[i - X]
        if window_sum > max_extra:
            max_extra = window_sum
    return base_satisfied + max_extra

easy

A. 2

B. 3

C. 4

D. 1

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand problem constraints

Step 2: Identify approach with linear time

Final Answer:

Quick Check:

Solution

Step 1: Calculate base_satisfied

Step 2: Initialize window_sum for first X=2 minutes

Step 3: Slide window from i=2 to 3

Final Answer:

Quick Check:

Solution

Step 1: Trace the deque and result for each iteration

Step 2: Collect final result

Final Answer:

Quick Check:

Solution

Step 1: Understand max_count usage

Step 2: Identify bug in max_count update

Final Answer:

Quick Check:

Solution

Step 1: Understand the new constraint

Step 2: Recognize sliding window limitation

Step 3: Use dynamic programming

Final Answer:

Quick Check:

Ready to prove it?