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. Consider the following code snippet for computing the maximum path sum in a binary tree. Given the tree with root value 1, left child 2, and right child 3, what is the final returned maximum path sum?

easy

A. 3

B. 6

C. 5

D. 4

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: Trace helper on left child (2):

Step 2: Trace helper on right child (3):

Step 3: Trace helper on root (1):

Final Answer:

Quick Check:

Solution

Step 1: Insert 1

Step 2: Insert 5

Step 3: Insert 3

Step 4: Find median

Final Answer:

Quick Check:

Solution

Step 1: Analyze sorting and offline queries

Step 2: Analyze trie operations

Final Answer:

Quick Check:

Solution

Step 1: Identify loops

Step 2: Calculate total operations

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse implications

Step 2: Prevent infinite recursion

Step 3: Evaluate options

Final Answer:

Quick Check:

Ready to prove it?