Minimum Window Substring in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Window Substring Function

What is the output of the following C# code that finds the minimum window substring?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static string MinWindow(string s, string t) {
        if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return "";
        Dictionary<char, int> dictT = new Dictionary<char, int>();
        foreach (char c in t) {
            dictT[c] = dictT.GetValueOrDefault(c, 0) + 1;
        }
        int required = dictT.Count;
        int l = 0, r = 0, formed = 0;
        Dictionary<char, int> windowCounts = new Dictionary<char, int>();
        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]);
    }

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

A "BANC"

B "CODEBA"

C "ADOBEC"

D "ABC"

💡 Hint

Think about the smallest substring in s that contains all characters of t.

The minimum window substring that contains all characters 'A', 'B', and 'C' in 'ADOBECODEBANC' is 'BANC'.

❓ Predict Output

intermediate

Output when target string has repeated characters

What is the output of the following C# code when the target string has repeated characters?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static string MinWindow(string s, string t) {
        if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t)) return "";
        Dictionary<char, int> dictT = new Dictionary<char, int>();
        foreach (char c in t) {
            dictT[c] = dictT.GetValueOrDefault(c, 0) + 1;
        }
        int required = dictT.Count;
        int l = 0, r = 0, formed = 0;
        Dictionary<char, int> windowCounts = new Dictionary<char, int>();
        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]);
    }

    static void Main() {
        string s = "AAABBC";
        string t = "AABC";
        Console.WriteLine(MinWindow(s, t));
    }
}

A "AABBC"

B "AABC"

C "ABBC"

D "AAAB"

💡 Hint

Remember the target has two 'A's, one 'B', and one 'C'.

The smallest substring containing two 'A's, one 'B', and one 'C' in 'AAABBC' is 'AABBC'.

🔧 Debug

advanced

Identify the error in the Minimum Window Substring code

What error will the following C# code produce when run?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static string MinWindow(string s, string t) {
        Dictionary<char, int> dictT = new Dictionary<char, int>();
        foreach (char c in t) {
            dictT[c] = dictT.GetValueOrDefault(c, 0) + 1;
        }
        int required = dictT.Count;
        int l = 0, r = 0, formed = 0;
        Dictionary<char, int> windowCounts = new Dictionary<char, int>();
        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]);
    }

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

A No error, outputs "BANC"

B KeyNotFoundException at dictT[c] = dictT[c] + 1;

C NullReferenceException at windowCounts[c] increment

D IndexOutOfRangeException at s.Substring call

💡 Hint

Check how dictionary keys are accessed and updated.

The code tries to increment dictT[c] without initializing the key c, causing a KeyNotFoundException.

🧠 Conceptual

advanced

Why use two pointers in Minimum Window Substring?

Why does the Minimum Window Substring algorithm use two pointers (left and right) to scan the string?

A To sort the string characters in ascending order before searching.

B To count the total number of characters in the string.

C To expand and contract the window dynamically to find the smallest substring containing all target characters.

D To reverse the string and compare with the target.

💡 Hint

Think about how the window changes size during the search.

Two pointers allow the window to grow and shrink, efficiently finding the minimum substring that contains all required characters.

🚀 Application

expert

Minimum Window Substring with Unicode Characters

Given the string s = "𝔸𝔹𝔸𝔻𝔹𝔸𝔻𝔸" and target t = "𝔸𝔻𝔹", what is the minimum window substring returned by a correct Minimum Window Substring algorithm that supports Unicode characters?

A "𝔸𝔹𝔸𝔻𝔹"

B "𝔸𝔹𝔸𝔻"

C "𝔸𝔻𝔹"

D "𝔹𝔸𝔻"

💡 Hint

Unicode characters may be multiple bytes but are treated as single characters in C# strings.

The smallest substring containing all characters '𝔸', '𝔻', and '𝔹' is '𝔹𝔸𝔻' starting at index 3.

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