Minimum Window Substring in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the left pointer for the sliding window.

DSA C#

int left = [1];

Drag options to blanks, or click blank then click option'

A1

B0

C-1

Ds.Length

Attempts:

3 left

💡 Hint

Common Mistakes

Starting left pointer at 1 skips the first character.

Using -1 causes index errors.

Setting left to s.Length is out of bounds.

The left pointer starts at index 0 to begin scanning the string from the start.

2fill in blank

medium

Complete the code to check if the current character is in the target frequency map.

DSA C#

if (targetFreq.ContainsKey(s[[1]]))

Drag options to blanks, or click blank then click option'

Aleft

Bcount

Ci

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using left pointer instead of right causes wrong character checks.

Using undefined variable i or count causes errors.

We check the character at the right pointer because the window expands from right to left.

3fill in blank

hard

Fix the error in updating the window counts after including a character.

DSA C#

windowCounts[s[[1]]] = windowCounts.GetValueOrDefault(s[[1]], 0) [2] 1;

Drag options to blanks, or click blank then click option'

Aleft

Bright

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using left pointer instead of right.

Subtracting instead of adding causes wrong counts.

We increase the count of the character at the right pointer by 1 in the window counts.

4fill in blank

hard

Fill both blanks to update the minimum window length and start index.

DSA C#

if (right - left + 1 < [1]) {
    minLen = right - left + 1;
    start = [2];
}

Drag options to blanks, or click blank then click option'

AminLen

Bleft

Cright

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting start to right instead of left.

Not updating minLen causes incorrect results.

We update minLen with the new smaller window size and start with the current left pointer.

5fill in blank

hard

Fill all three blanks to shrink the window and update counts correctly.

DSA C#

char c = s[[1]];
windowCounts[c] = windowCounts[c] [2] 1;
left = [3] + 1;

Drag options to blanks, or click blank then click option'

Aleft

B-

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using right pointer instead of left to remove character.

Adding instead of subtracting counts.

Not moving left pointer forward.

We remove the character at left from the window by decreasing its count and move left pointer forward.

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