Minimum Window Substring in DSA C# - Deep Dive

Overview - Minimum Window Substring

What is it?

Minimum Window Substring is a problem where you find the smallest part of a string that contains all characters of another string. Imagine you have two strings, and you want to find the shortest piece of the first string that has every letter from the second string. This helps in searching and matching tasks where you want to find a compact match.

Why it matters

Without this concept, searching for the smallest matching segment would be slow and inefficient, especially in large texts. It solves the problem of quickly finding the minimal section that contains all needed characters, which is useful in text processing, DNA sequencing, and search engines. Without it, many applications would waste time scanning unnecessarily large parts of data.

Where it fits

Before learning this, you should understand basic string handling and hash maps (dictionaries). After this, you can explore sliding window techniques and advanced string algorithms like substring search and pattern matching.

Mental Model

Core Idea

Find the smallest window in a string that contains all characters of another string by expanding and shrinking a sliding window while tracking character counts.

Think of it like...

It's like packing a suitcase with all your travel essentials: you start by throwing in items until you have everything, then try to remove unnecessary things to make the suitcase as small as possible without losing anything important.

String:  A B C D E F G H I J
Target:  C F G

Window moves:
[ A B C D E F ] G H I J  -> contains C, F but missing G
[ B C D E F G ] H I J    -> contains C, F, G (valid)
Shrink window from left to find minimum:
[ C D E F G ]             -> still valid
[ D E F G ]               -> missing C, stop

Minimum window: C D E F G

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Introduce the problem of finding a substring containing all characters of another string.

Given two strings, source and target, we want to find the smallest substring in source that contains all characters from target, including duplicates. For example, if source is "ADOBECODEBANC" and target is "ABC", the answer is "BANC" because it contains A, B, and C and is the shortest such substring.

Result

Clear understanding of the problem and what output is expected.

Understanding the problem clearly is essential before jumping into solutions to avoid confusion about what 'minimum window' means.

2

Foundation

Counting Characters with Dictionaries

Concept: Use dictionaries to count how many times each character appears in the target string.

Create a dictionary to store the count of each character in the target string. For example, for target "AABC", the dictionary is { 'A': 2, 'B': 1, 'C': 1 }. This helps track what characters and how many of each we need to find in the source string.

Result

A character frequency map for the target string.

Knowing exactly what and how many characters to look for is the foundation for checking if a window is valid.

3

Intermediate

Sliding Window Expansion

🤔Before reading on: do you think expanding the window from left to right alone is enough to find the minimum substring? Commit to yes or no.

Concept: Expand the window by moving the right pointer to include characters until all target characters are found.

Start with two pointers at the beginning of the source string. Move the right pointer forward, adding characters to the current window count. When the window contains all characters needed (checked by comparing counts), stop expanding.

Result

A window that contains all characters of the target, but not necessarily the smallest.

Expanding the window helps find a valid substring, but it may not be minimal yet.

4

Intermediate

Sliding Window Shrinking

🤔Before reading on: do you think shrinking the window from the left can help find a smaller valid substring? Commit to yes or no.

Concept: Shrink the window from the left to remove unnecessary characters while keeping it valid.

Once a valid window is found, move the left pointer forward to remove characters that are not needed or are extra. Update counts accordingly. Stop shrinking when the window no longer contains all required characters.

Result

A smaller valid window, closer to the minimum substring.

Shrinking the window removes extra characters, helping find the smallest valid substring.

5

Intermediate

Tracking the Minimum Window

Concept: Keep track of the smallest window found during the process.

Each time a valid window is found, compare its size with the smallest window recorded so far. Update the minimum window if the current one is smaller. Continue expanding and shrinking until the end of the source string.

Result

The smallest window substring containing all target characters.

Tracking the minimum window ensures the final answer is the shortest possible substring.

6

Advanced

Optimizing with Character Counts and Matches

🤔Before reading on: do you think checking all characters every time is efficient? Commit to yes or no.

Concept: Use a match count to avoid checking all characters repeatedly.

Maintain a count of how many target characters have been matched in the current window. Increase match count when a needed character's count matches the target count. Decrease when shrinking removes a needed character. This avoids scanning the entire dictionary each time.

Result

More efficient checking of window validity, improving performance.

Using a match count reduces unnecessary checks, making the algorithm faster.

7

Expert

Handling Edge Cases and Unicode

🤔Before reading on: do you think this algorithm works the same for all character sets? Commit to yes or no.

Concept: Consider edge cases like empty strings, repeated characters, and Unicode characters.

Handle cases where target or source is empty, or target has characters not in source. Also, ensure the algorithm works with Unicode by using appropriate data structures. For example, using dictionaries keyed by characters supports Unicode naturally.

Result

Robust algorithm that works correctly in all cases.

Accounting for edge cases and character sets prevents bugs and ensures real-world usability.

Under the Hood

The algorithm uses two pointers to create a sliding window over the source string. It keeps track of character counts inside the window and compares them to the target counts. When the window contains all required characters, it tries to shrink from the left to find the smallest valid window. Internally, dictionaries store counts, and a match count tracks how many characters meet the required frequency. This approach avoids checking the entire window repeatedly, making it efficient.

Why designed this way?

This method was designed to solve the problem in linear time, avoiding the costly brute force approach that checks all substrings. The sliding window technique balances expanding and shrinking to find minimal windows efficiently. Alternatives like nested loops are slower and impractical for large strings.

Source string:  [left]----------------[right]
                 |                     |
                 v                     v
               Window expands -> includes chars
               Window shrinks -> removes extra chars

Character counts tracked in dictionaries
Match count tracks how many chars meet target frequency
When match count equals target unique chars, window is valid

Myth Busters - 3 Common Misconceptions

Quick: Do you think the minimum window substring always starts at the first occurrence of a target character? Commit yes or no.

Common Belief: The minimum window substring must start at the first occurrence of one of the target characters.

Reality: The minimum window can start anywhere; it is found by expanding and shrinking the window, not just by the first occurrence.

Why it matters: Assuming it starts at the first occurrence can cause missing smaller valid windows later in the string.

Quick: Do you think checking the entire window's characters every time is necessary? Commit yes or no.

Common Belief: You must check all characters in the current window every time to see if it contains the target.

Reality: Using a match count and character frequency maps lets you check validity efficiently without scanning the whole window each time.

Why it matters: Checking the whole window repeatedly leads to inefficient algorithms that are too slow for large inputs.

Quick: Do you think the algorithm works the same for Unicode characters as for ASCII? Commit yes or no.

Common Belief: The algorithm only works for ASCII characters and breaks with Unicode.

Reality: By using dictionaries keyed by characters, the algorithm naturally supports Unicode characters as well.

Why it matters: Ignoring Unicode support limits the algorithm's usefulness in real-world applications with diverse character sets.

Expert Zone

1

The order of characters in the target string does not matter; only their counts do.

2

When shrinking the window, removing a character that is not needed or is extra does not affect validity, so shrinking can continue.

3

Using two dictionaries--one for target counts and one for current window counts--helps manage character frequencies cleanly and avoid bugs.

When NOT to use

This approach is not suitable when the order of characters matters, such as in substring search with sequence constraints. For such cases, algorithms like KMP or suffix automata are better. Also, if the target string is very large compared to the source, other heuristics might be more efficient.

Production Patterns

In production, this algorithm is used in text editors for search features, bioinformatics for DNA sequence matching, and search engines for query matching. It is often combined with caching and preprocessing to handle repeated queries efficiently.

Connections

Sliding Window Technique

Minimum Window Substring is a classic example of the sliding window technique.

Understanding this problem deeply helps grasp the sliding window pattern used in many other algorithms for arrays and strings.

Hash Maps (Dictionaries)

Uses hash maps to count and track characters efficiently.

Knowing how to use dictionaries for frequency counting is essential for implementing this and many other string algorithms.

Inventory Management

Both involve tracking quantities of items and adjusting stock levels.

The way the algorithm tracks character counts and matches is similar to managing inventory levels in a warehouse, showing how computer science concepts mirror real-world systems.

Common Pitfalls

#1 Not updating character counts correctly when shrinking the window.

Wrong approach:

if (windowCounts[char] > 0) windowCounts[char]--;
left++;

Correct approach:

windowCounts[char]--;
if (windowCounts[char] < targetCounts[char]) matched--;
left++;

Root cause:

Failing to decrease the matched count when removing a needed character causes the algorithm to think the window is still valid when it is not.

#2 Checking window validity by scanning the entire dictionary every time.

Wrong approach:

bool isValid() {
foreach (var c in targetCounts.Keys) {
if (windowCounts[c] < targetCounts[c]) return false;
}
return true;
}

Correct approach:

Use a matched count variable that increments/decrements as characters are added/removed, avoiding full scans.

Root cause:

Inefficient checking leads to slow performance, especially for large strings.

#3 Not handling empty strings or target characters not in source.

Wrong approach:

Assuming source and target are non-empty and all target chars appear in source without checks.

Correct approach:

if (string.IsNullOrEmpty(source) || string.IsNullOrEmpty(target)) return "";
// Also check if target chars exist in source before processing.

Root cause:

Ignoring edge cases causes runtime errors or incorrect results.

Key Takeaways

Minimum Window Substring finds the smallest part of a string containing all characters of another string using a sliding window.

Using dictionaries to count characters and a match count to track validity makes the algorithm efficient.

Expanding and shrinking the window carefully helps find the minimal valid substring without checking all substrings.

Handling edge cases and character sets like Unicode ensures the algorithm works correctly in real-world scenarios.

Understanding this problem deeply builds a foundation for many other string and sliding window algorithms.

Practice

1. What does the "Minimum Window Substring" problem ask you to find given two strings s and t?

easy

A. The substring of s that is exactly equal to t

B. The longest substring in s that does not contain any character of t

C. The number of times t appears in s

D. The smallest substring in s that contains all characters of t

Solution

1. Step 1: Understand the problem goal

   The problem asks to find the smallest part of string s that includes every character from string t at least once.

2. Step 2: Compare options with the problem goal

   The smallest substring in s that contains all characters of t matches the goal exactly. The longest substring without characters from t, the count of t appearances, or exact equality to t describe unrelated problems.

3. Final Answer:

   The smallest substring in s that contains all characters of t -> Option D

4. Quick Check:

   Minimum window substring = smallest substring containing all chars [OK]

Hint: Look for smallest substring covering all chars of t [OK]

Common Mistakes:

• Confusing minimum window with longest substring
• Thinking it counts occurrences instead of covering characters
• Assuming substring must be equal to t

2. Which of the following C# code snippets correctly initializes a dictionary to count characters of string t for the Minimum Window Substring problem?

easy

A. var dict = new Dictionary(); foreach (var c in t) { dict.Add(c, 1); }

B. var dict = new Dictionary(); foreach (var c in t) { dict[c] = dict.GetValueOrDefault(c, 0) + 1; }

C. var dict = new Dictionary(); foreach (var c in t) { dict.Add(c, 1); }

D. var dict = new Dictionary(); foreach (var c in t) { dict[c] += 1; }

Solution

1. Step 1: Check dictionary type and initialization

   Dictionary<char, int> is correct for counting characters. Dictionary<int, char> uses wrong types. Adding keys with Add fails on duplicates in t. Incrementing with += on uninitialized keys causes exceptions.

2. Step 2: Verify counting logic

   GetValueOrDefault(c, 0) + 1 safely handles missing keys and increments correctly for duplicates. Add(c, 1) throws on duplicates. dict[c] += 1 throws KeyNotFoundException on first occurrence.

3. Final Answer:

   var dict = new Dictionary<char, int>(); foreach (var c in t) { dict[c] = dict.GetValueOrDefault(c, 0) + 1; } -> Option B

4. Quick Check:

   Correct dictionary initialization and counting = var dict = new Dictionary(); foreach (var c in t) { dict[c] = dict.GetValueOrDefault(c, 0) + 1; } [OK]

Hint: Use GetValueOrDefault to safely increment dictionary counts [OK]

Common Mistakes:

• Using wrong dictionary key/value types
• Adding duplicate keys without checking
• Incrementing dictionary values without initialization

3. What is the output of the following C# code snippet for the Minimum Window Substring problem?

string s = "ADOBECODEBANC";
string t = "ABC";
string result = MinWindow(s, t);
Console.WriteLine(result);

string MinWindow(string s, string t) {
    var dictT = new Dictionary();
    foreach (var c in t) dictT[c] = dictT.GetValueOrDefault(c, 0) + 1;
    int required = dictT.Count;
    int l = 0, r = 0, formed = 0;
    var windowCounts = new Dictionary();
    int[] ans = {-1, 0, 0};
    while (r < s.Length) {
        char c = s[r];
        windowCounts[c] = windowCounts.GetValueOrDefault(c, 0) + 1;
        if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c]) formed++;
        while (l <= r && formed == required) {
            c = s[l];
            if (ans[0] == -1 || r - l + 1 < ans[0]) {
                ans[0] = r - l + 1;
                ans[1] = l;
                ans[2] = r;
            }
            windowCounts[c]--;
            if (dictT.ContainsKey(c) && windowCounts[c] < dictT[c]) formed--;
            l++;
        }
        r++;
    }
    return ans[0] == -1 ? "" : s.Substring(ans[1], ans[0]);
}

medium

A. "CODEBA"

B. "ADOBEC"

C. "BANC"

D. "ABC"

Solution

1. Step 1: Understand the sliding window logic

   The code uses two pointers to find the smallest substring in s containing all chars of t. It expands right pointer r to include chars and moves left pointer l to minimize window while keeping all required chars.

2. Step 2: Trace the example input

   For s = "ADOBECODEBANC" and t = "ABC", the minimum window substring containing 'A', 'B', and 'C' is "BANC" starting at index 9 with length 4.

3. Final Answer:

   "BANC" -> Option C

4. Quick Check:

   Minimum window substring for given input = "BANC" [OK]

Hint: Use sliding window to track counts and minimize substring [OK]

Common Mistakes:

• Returning first found substring instead of minimum
• Not updating minimum window when smaller found
• Incorrectly updating counts causing wrong formed count

4. Identify the bug in the following C# code snippet for Minimum Window Substring and select the fix.

string MinWindow(string s, string t) {
    var dictT = new Dictionary();
    foreach (var c in t) dictT[c] = dictT.GetValueOrDefault(c, 0) + 1;
    int required = dictT.Count;
    int l = 0, r = 0, formed = 0;
    var windowCounts = new Dictionary();
    int[] ans = {-1, 0, 0};
    while (r < s.Length) {
        char c = s[r];
        windowCounts[c] = windowCounts.GetValueOrDefault(c, 0) + 1;
        if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c]) formed++;
        while (l <= r && formed == required) {
            c = s[l];
            if (ans[0] == -1 || r - l + 1 < ans[0]) {
                ans[0] = r - l + 1;
                ans[1] = l;
                ans[2] = r;
            }
            windowCounts[c]--;
            if (dictT.ContainsKey(c) && windowCounts[c] <= dictT[c]) formed--;
            l++;
        }
        r++;
    }
    return ans[0] == -1 ? "" : s.Substring(ans[1], ans[0]);
}

medium

A. Change condition from windowCounts[c] <= dictT[c] to windowCounts[c] < dictT[c] when decreasing formed

B. Initialize formed to 1 instead of 0

C. Remove the inner while loop to avoid infinite loop

D. Change ans array size to 4 elements

Solution

1. Step 1: Analyze the condition for decreasing formed count

   The bug is in the line if (dictT.ContainsKey(c) && windowCounts[c] <= dictT[c]) formed--;. Using <= causes formed to decrease even when counts are equal, prematurely reducing formed.

2. Step 2: Correct the condition to strictly less than

   Changing condition to windowCounts[c] < dictT[c] ensures formed decreases only when count falls below required, fixing the bug.

3. Final Answer:

   Change condition from windowCounts[c] <= dictT[c] to windowCounts[c] < dictT[c] when decreasing formed -> Option A

4. Quick Check:

   Strict less than fixes formed decrement bug [OK]

Hint: Use < than, not <=, when checking counts to reduce formed [OK]

Common Mistakes:

• Using <= instead of < causing wrong formed count
• Incorrect initialization of formed variable
• Removing inner loop causing incorrect window shrinking

5. Given strings s = "aabbccdd" and t = "abc", what is the minimum window substring that contains all characters of t? Consider that characters can appear multiple times in s but only once in t.

hard

A. "aabbcc"

B. "abc"

C. "bcca"

D. "abbc"

Solution

1. Step 1: Identify required characters and counts

   String t requires one 'a', one 'b', and one 'c'. We need the smallest substring in s containing at least one of each.

2. Step 2: Find minimum substring in s covering all required chars

   Checking substrings: "aabbcc" (positions 0 to 5) contains 'a', 'b', and 'c' at least once each and is the smallest substring covering all required characters. "abbc" (positions 1 to 4) misses 'c' at position 4 (which is 'b'), so it does not contain 'c'. "abc" does not appear consecutively. "bcca" is not a substring in order. So "aabbcc" is the smallest valid window.

3. Final Answer:

   "aabbcc" -> Option A

4. Quick Check:

   Minimum window substring with all chars = "aabbcc" [OK]

Hint: Check all substrings covering t chars, pick shortest [OK]

Common Mistakes:

• Choosing substring missing one required character
• Picking substring with correct chars but longer length
• Ignoring character counts in t