Minimum Window Substring in DSA C#

Mental Model

Find the smallest part of a big string that contains all characters of a smaller string. We slide a window over the big string and adjust it to keep all needed characters while trying to shrink it.

Analogy: Imagine you have a long necklace with many beads and you want to find the shortest segment that contains all colors from a small set of beads you need. You move your fingers along the necklace, stretching and shrinking the segment until you find the smallest one with all colors.

big string: [A] -> [D] -> [O] -> [B] -> [E] -> [C] -> [O] -> [D] -> [E] -> [B] -> [A] -> [N] -> [C] -> [E] -> null
window: ↑--------------------↑
need: {A:1, B:1, C:1}
have: {A:1, B:1, C:0}

Dry Run Walkthrough

Input: big string: "ADOBECODEBANC", small string: "ABC"

Goal: Find the smallest substring in "ADOBECODEBANC" that contains all characters 'A', 'B', and 'C'.

Step 1: Expand window right pointer to include 'A' at index 0

Window: [A] -> null
Have: {A:1}, Need: {A:1, B:1, C:1}

Why: Start including characters to cover needed ones

Step 2: Expand right pointer to include 'D' at index 1

Window: [A] -> [D] -> null
Have: {A:1}, Need: {A:1, B:1, C:1}

Why: 'D' is not needed, keep expanding

Step 3: Expand right pointer to include 'O' at index 2

Window: [A] -> [D] -> [O] -> null
Have: {A:1}, Need: {A:1, B:1, C:1}

Why: 'O' is not needed, keep expanding

Step 4: Expand right pointer to include 'B' at index 3

Window: [A] -> [D] -> [O] -> [B] -> null
Have: {A:1, B:1}, Need: {A:1, B:1, C:1}

Why: Found 'B', closer to covering all needed chars

Step 5: Expand right pointer to include 'E' at index 4

Window: [A] -> [D] -> [O] -> [B] -> [E] -> null
Have: {A:1, B:1}, Need: {A:1, B:1, C:1}

Why: 'E' not needed, keep expanding

Step 6: Expand right pointer to include 'C' at index 5

Window: [A] -> [D] -> [O] -> [B] -> [E] -> [C] -> null
Have: {A:1, B:1, C:1}, Need: {A:1, B:1, C:1}

Why: All needed chars found, try shrinking window

Step 7: Shrink left pointer from 'A' at index 0

Window: [D] -> [O] -> [B] -> [E] -> [C] -> null
Have: {A:0, B:1, C:1}, Need: {A:1, B:1, C:1}

Why: Removing 'A' breaks requirement, stop shrinking

Step 8: Expand right pointer to include 'O' at index 6

Window: [D] -> [O] -> [B] -> [E] -> [C] -> [O] -> null
Have: {A:0, B:1, C:1}, Need: {A:1, B:1, C:1}

Why: Continue scanning for smaller window

Step 9: Shrink left pointer from 'D' at index 1

Window: [O] -> [B] -> [E] -> [C] -> [O] -> null
Have: {A:0, B:1, C:1}, Need: {A:1, B:1, C:1}

Why: 'D' not needed, shrink window

Step 10: Shrink left pointer from 'O' at index 2

Window: [B] -> [E] -> [C] -> [O] -> null
Have: {A:0, B:1, C:1}, Need: {A:1, B:1, C:1}

Why: 'O' not needed, shrink window

Step 11: Shrink left pointer from 'B' at index 3

Window: [E] -> [C] -> [O] -> null
Have: {A:0, B:0, C:1}, Need: {A:1, B:1, C:1}

Why: Removing 'B' breaks requirement, stop shrinking

Step 12: Expand right pointer to include 'D' at index 7

Window: [E] -> [C] -> [O] -> [D] -> null
Have: {A:0, B:0, C:1}, Need: {A:1, B:1, C:1}

Why: 'D' not needed, keep expanding

Step 13: Expand right pointer to include 'E' at index 8

Window: [E] -> [C] -> [O] -> [D] -> [E] -> null
Have: {A:0, B:0, C:1}, Need: {A:1, B:1, C:1}

Why: 'E' not needed, keep expanding

Step 14: Expand right pointer to include 'B' at index 9

Window: [E] -> [C] -> [O] -> [D] -> [E] -> [B] -> null
Have: {A:0, B:1, C:1}, Need: {A:1, B:1, C:1}

Why: Found 'B' again, all needed chars present

Step 15: Shrink left pointer from 'E' at index 4

Window: [C] -> [O] -> [D] -> [E] -> [B] -> null
Have: {A:0, B:1, C:1}, Need: {A:1, B:1, C:1}

Why: 'E' not needed, shrink window

Step 16: Shrink left pointer from 'C' at index 5

Window: [O] -> [D] -> [E] -> [B] -> null
Have: {A:0, B:1, C:0}, Need: {A:1, B:1, C:1}

Why: Removing 'C' breaks requirement, stop shrinking

Step 17: Expand right pointer to include 'A' at index 10

Window: [O] -> [D] -> [E] -> [B] -> [A] -> null
Have: {A:1, B:1, C:0}, Need: {A:1, B:1, C:1}

Why: Found 'A' again, but still missing 'C'

Step 18: Expand right pointer to include 'N' at index 11

Window: [O] -> [D] -> [E] -> [B] -> [A] -> [N] -> null
Have: {A:1, B:1, C:0}, Need: {A:1, B:1, C:1}

Why: 'N' not needed, keep expanding

Step 19: Expand right pointer to include 'C' at index 12

Window: [O] -> [D] -> [E] -> [B] -> [A] -> [N] -> [C] -> null
Have: {A:1, B:1, C:1}, Need: {A:1, B:1, C:1}

Why: All needed chars present again, try shrinking

Step 20: Shrink left pointer from 'O' at index 6

Window: [D] -> [E] -> [B] -> [A] -> [N] -> [C] -> null
Have: {A:1, B:1, C:1}, Need: {A:1, B:1, C:1}

Why: 'O' not needed, shrink window

Step 21: Shrink left pointer from 'D' at index 7

Window: [E] -> [B] -> [A] -> [N] -> [C] -> null
Have: {A:1, B:1, C:1}, Need: {A:1, B:1, C:1}

Why: 'D' not needed, shrink window

Step 22: Shrink left pointer from 'E' at index 8

Window: [B] -> [A] -> [N] -> [C] -> null
Have: {A:1, B:1, C:1}, Need: {A:1, B:1, C:1}

Why: 'E' not needed, shrink window

Step 23: Shrink left pointer from 'B' at index 9

Window: [A] -> [N] -> [C] -> null
Have: {A:1, B:0, C:1}, Need: {A:1, B:1, C:1}

Why: Removing 'B' breaks requirement, stop shrinking

Step 24: Shrink left pointer from 'A' at index 10

Window: [N] -> [C] -> null
Have: {A:0, B:0, C:1}, Need: {A:1, B:1, C:1}

Why: Removing 'A' breaks requirement, stop shrinking

Result:

Window: [B] -> [A] -> [N] -> [C] -> null
Smallest substring: "BANC"

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Solution {
    public static string MinWindow(string s, string t) {
        if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return "";

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

        int have = 0, needCount = need.Count;
        Dictionary<char, int> window = new Dictionary<char, int>();
        int left = 0, minLen = int.MaxValue, minStart = 0;

        for (int right = 0; right < s.Length; right++) {
            char c = s[right];
            window[c] = window.GetValueOrDefault(c, 0) + 1;

            if (need.ContainsKey(c) && window[c] == need[c]) {
                have++;
            }

            while (have == needCount) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }

                char leftChar = s[left];
                window[leftChar]--;
                if (need.ContainsKey(leftChar) && window[leftChar] < need[leftChar]) {
                    have--;
                }
                left++;
            }
        }

        return minLen == int.MaxValue ? "" : s.Substring(minStart, minLen);
    }

    static void Main() {
        string s = "ADOBECODEBANC";
        string t = "ABC";
        string result = MinWindow(s, t);
        Console.WriteLine(result);
    }
}

foreach (char c in t) { need[c] = need.GetValueOrDefault(c, 0) + 1; }

Count needed characters from t

window[c] = window.GetValueOrDefault(c, 0) + 1;

Add current character to window count

if (need.ContainsKey(c) && window[c] == need[c]) { have++; }

Increase have when a needed char count matches requirement

while (have == needCount) {

Try shrinking window while all needed chars are present

if (right - left + 1 < minLen) { minLen = right - left + 1; minStart = left; }

Update minimum window size and start index

window[leftChar]--; if (need.ContainsKey(leftChar) && window[leftChar] < need[leftChar]) { have--; } left++;

Shrink window from left and update have if requirement breaks

Output

BANC

Complexity Analysis

Time: O(n) because each character in the big string is visited at most twice by left and right pointers

Space: O(m) where m is the size of the smaller string t for storing needed character counts

vs Alternative: Naive approach checks all substrings leading to O(n^2) or worse; sliding window reduces it to linear time

Edge Cases

Empty big string or empty small string

Returns empty string immediately

DSA C#

if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return "";

Small string characters not in big string

No valid window found, returns empty string

DSA C#

return minLen == int.MaxValue ? "" : s.Substring(minStart, minLen);

Small string with repeated characters

Counts needed characters correctly and finds window covering all repeats

DSA C#

need[c] = need.GetValueOrDefault(c, 0) + 1;

When to Use This Pattern

When asked to find the smallest substring containing all characters of another string, use the sliding window pattern with two pointers and a frequency map to efficiently track coverage.

Common Mistakes

Mistake: Not updating the 'have' count correctly when shrinking the window
Fix: Decrease 'have' only when a needed character count in window falls below required count

Mistake: Shrinking window without checking if all needed characters are still covered
Fix: Only shrink window inside while(have == needCount) loop to maintain coverage

Summary

Finds the smallest substring in a big string that contains all characters of a smaller string.

Use when you need to find a minimal window covering all required characters efficiently.

Use two pointers to expand and shrink a window while tracking character counts to find the minimum window.

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