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. You are given an integer array and a number k. You need to count the number of contiguous subarrays that contain exactly k odd numbers. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Use dynamic programming to store counts of subarrays ending at each index with exactly k odd numbers.

B. Use a brute force nested loop to check all subarrays and count odd numbers.

C. Use a sliding window with two pointers to count subarrays with at most k and k-1 odd numbers and subtract.

D. Use a greedy approach to expand and shrink the window whenever the odd count exceeds k.

2. Consider the following code snippet implementing the optimal prefix sum with hash map approach. What is the final returned value when the input is nums = [1, 2, 3] and k = 3?

def subarraySum(nums, k):
    count = 0
    running_sum = 0
    prefix_counts = {0: 1}
    for num in nums:
        running_sum += num
        if running_sum - k in prefix_counts:
            count += prefix_counts[running_sum - k]
        prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
    return count

print(subarraySum([1, 2, 3], 3))

easy

A. 3

B. 0

C. 1

D. 2

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 the problem constraints

Step 2: Evaluate approaches

Final Answer:

Quick Check:

Solution

Step 1: Trace running_sum and prefix_counts

Step 2: Return count

Final Answer:

Quick Check:

Solution

Step 1: Understand the role of seen dictionary initialization

Step 2: Identify that initializing seen as empty misses subarrays starting at index 0

Final Answer:

Quick Check:

Solution

Step 1: Analyze frequency update when complement found

Step 2: Identify incorrect increment

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse and input size impact

Step 2: Identify efficient data structure

Step 3: Confirm approach correctness

Final Answer:

Quick Check:

Ready to prove it?