Minimum Window Substring in DSA C# - Build from Scratch

Minimum Window Substring

📖 Scenario: Imagine you are working on a text analysis tool. You need to find the smallest part of a text that contains all the important keywords. This helps highlight the most relevant snippet quickly.

🎯 Goal: Build a program that finds the minimum window substring in a given string s that contains all characters of another string t.

📋 What You'll Learn

Create a string variable s with the value "ADOBECODEBANC".

Create a string variable t with the value "ABC".

Create a dictionary called dictT to count characters in t.

Create variables required, formed, left, right, and ans to help find the minimum window.

Use a sliding window approach with two pointers left and right to find the minimum substring.

Print the minimum window substring found.

💡 Why This Matters

🌍 Real World

Finding the smallest snippet in a document that contains all keywords is useful in search engines and text summarization.

💼 Career

Understanding sliding window techniques and dictionary usage is important for software engineers working on text processing, search algorithms, and performance optimization.

1

Setup input strings s and t

Create two string variables: s with the value "ADOBECODEBANC" and t with the value "ABC".

DSA C#

# Create string variables s and t with given values
# Your code here

Hint

Use string s = "ADOBECODEBANC"; and string t = "ABC"; to create the variables.

2

Create dictionary dictT to count characters in t

Create a Dictionary<char, int> called dictT and count each character in t using a foreach loop.

DSA C#

string s = "ADOBECODEBANC";
string t = "ABC";

// Create dictT and count characters in t
// Your code here

Hint

Use a dictionary to count characters. For each character in t, increase its count or add it if not present.

3

Implement sliding window to find minimum substring

Implement the sliding window logic using variables required, formed, left, right, and a dictionary windowCounts. Use a while loop to expand right and a nested while loop to contract left when conditions are met. Update ans tuple to track the smallest window.

DSA C#

string s = "ADOBECODEBANC";
string t = "ABC";

Dictionary dictT = new Dictionary();
foreach (char c in t)
{
    if (dictT.ContainsKey(c))
        dictT[c]++;
    else
        dictT[c] = 1;
}

// Implement sliding window to find minimum substring
// Your code here

Hint

Use two pointers left and right to expand and contract the window. Track counts in windowCounts and update formed when counts match.

4

Print the minimum window substring

Print the substring of s from ans.start to ans.end if ans.length is not int.MaxValue. Otherwise, print an empty string.

DSA C#

string s = "ADOBECODEBANC";
string t = "ABC";

Dictionary dictT = new Dictionary();
foreach (char c in t)
{
    if (dictT.ContainsKey(c))
        dictT[c]++;
    else
        dictT[c] = 1;
}

int required = dictT.Count;
int formed = 0;

Dictionary windowCounts = new Dictionary();

int left = 0, right = 0;

(int length, int start, int end) ans = (int.MaxValue, 0, 0);

while (right < s.Length)
{
    char c = s[right];
    if (windowCounts.ContainsKey(c))
        windowCounts[c]++;
    else
        windowCounts[c] = 1;

    if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c])
        formed++;

    while (left <= right && formed == required)
    {
        c = s[left];

        if (right - left + 1 < ans.length)
            ans = (right - left + 1, left, right);

        windowCounts[c]--;
        if (dictT.ContainsKey(c) && windowCounts[c] < dictT[c])
            formed--;

        left++;
    }

    right++;
}

// Print the minimum window substring
// Your code here

Hint

Use Console.WriteLine to print the substring from ans.start with length ans.length. If no valid window, print empty string.

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