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.

Analogy: Imagine searching for all ingredients of a recipe in a long shelf of spices. You pick a small box and move it along the shelf, making it bigger or smaller to hold all ingredients with no extras.

Big string: [A B C D E F G H I J]
Window:      ↑       ↑
             start   end
Needed chars: [A B C]
Window contains: A B C D E

Dry Run Walkthrough

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

Goal: Find the smallest substring in big string containing all characters A, B, and C

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

"[A]DOBECODEBANC" start=0 end=0 window='A'

Why: Start building window to include needed chars

Step 2: Expand window end to include 'D', 'O', 'B', 'E', 'C' up to index 5

"[A D O B E C]ODEBANC" start=0 end=5 window='ADOBEC'

Why: Window now contains all needed chars A, B, C

Step 3: Shrink window start to remove 'A' at index 0

"A[D O B E C]ODEBANC" start=1 end=5 window='DOBEC'

Why: Try to reduce window size while keeping all needed chars

Step 4: Expand window end to include 'O', 'D', 'E', 'B', 'A', 'N', 'C' up to index 12

"ADO[B E C O D E B A N C]" start=1 end=12 window='DOBECODEBANC'

Why: Find another window containing all needed chars

Step 5: Shrink window start to remove 'D', 'O', 'B', 'E' until start=9

"ADOBECODE[B A N C]" start=9 end=12 window='BANC'

Why: Shrink to smallest window containing all needed chars

Result:

"BANC" is the smallest substring containing A, B, and C

Annotated Code

DSA C

#include <stdio.h>
#include <string.h>
#include <limits.h>

#define CHAR_RANGE 128

char* minWindow(char* s, char* t) {
    int need[CHAR_RANGE] = {0};
    int window[CHAR_RANGE] = {0};
    int left = 0, right = 0, valid = 0;
    int start = 0, min_len = INT_MAX;
    int t_len = strlen(t);
    int s_len = strlen(s);

    for (int i = 0; i < t_len; i++) {
        need[(int)t[i]]++;
    }
    int required = 0;
    for (int i = 0; i < CHAR_RANGE; i++) {
        if (need[i] > 0) {
            required++;
        }
    }

    while (right < s_len) {
        char c = s[right];
        right++;
        if (need[(int)c] > 0) {
            window[(int)c]++;
            if (window[(int)c] == need[(int)c]) {
                valid++;
            }
        }

        while (valid == required) {
            if (right - left < min_len) {
                start = left;
                min_len = right - left;
            }
            char d = s[left];
            left++;
            if (need[(int)d] > 0) {
                if (window[(int)d] == need[(int)d]) {
                    valid--;
                }
                window[(int)d]--;
            }
        }
    }

    if (min_len == INT_MAX) {
        return "";
    }

    static char res[1000];
    strncpy(res, s + start, min_len);
    res[min_len] = '\0';
    return res;
}

int main() {
    char s[] = "ADOBECODEBANC";
    char t[] = "ABC";
    char* result = minWindow(s, t);
    printf("%s\n", result);
    return 0;
}

for (int i = 0; i < t_len; i++) { need[(int)t[i]]++; }

Count needed characters from t

while (right < s_len) { char c = s[right]; right++; if (need[(int)c] > 0) { window[(int)c]++; if (window[(int)c] == need[(int)c]) { valid++; } }

Expand window right pointer and update counts

while (valid == required) { if (right - left < min_len) { start = left; min_len = right - left; }

Check if current window contains all needed chars and update minimum

char d = s[left]; left++; if (need[(int)d] > 0) { if (window[(int)d] == need[(int)d]) { valid--; } window[(int)d]--; } }

Shrink window from left to find smaller valid window

if (min_len == INT_MAX) { return ""; }

Return empty if no valid window found

strncpy(res, s + start, min_len); res[min_len] = '\0'; return res;

Copy minimum window substring to result

Output

BANC

Complexity Analysis

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

Space: O(1) because the character count arrays have fixed size (128 ASCII chars)

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 (min_len == INT_MAX) { return ""; }

Small string characters not in big string

No valid window found, returns empty string

DSA C

if (min_len == INT_MAX) { return ""; }

Small string with repeated characters

Window counts ensure all repeated chars are included before valid

DSA C

if (window[(int)c] == need[(int)c]) { valid++; }

When to Use This Pattern

When you need the smallest substring containing all characters of another string, use the sliding window pattern to efficiently find it.

Common Mistakes

Mistake: Counting valid characters incorrectly by only checking presence, not counts
Fix: Track counts of each character and only increase valid when counts match needed counts

Mistake: Shrinking window too early before all needed chars are included
Fix: Only shrink window when all needed chars are fully included (valid == required)

Summary

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

Use when you want to find a minimal window containing all required characters efficiently.

The key is to expand and shrink a sliding window while tracking character counts to maintain validity.

Practice

1. What is the main goal of the Minimum Window Substring problem?

easy

A. Find the smallest substring in a string that contains all characters of another string

B. Count the total number of substrings in a string

C. Find the longest substring without repeating characters

D. Sort the characters of a string in ascending order

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the smallest part of a string that includes all characters from another string.

2. Step 2: Compare options with the problem goal

   Only Find the smallest substring in a string that contains all characters of another string matches the goal of finding the smallest substring containing all characters of another string.

3. Final Answer:

   Find the smallest substring in a string that contains all characters of another string -> Option A

4. Quick Check:

   Minimum Window Substring = Smallest substring containing all chars [OK]

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

Common Mistakes:

• Confusing with longest substring problems
• Thinking it counts substrings instead of finding minimum
• Mixing sorting with substring search

2. Which of the following C code snippets correctly initializes a frequency array for characters in the Minimum Window Substring problem?

easy

A. int freq[256] = {0};

B. int freq[26]; for(int i=0; i<26; i++) freq[i] = -1;

C. int freq[128]; memset(freq, 1, sizeof(freq));

D. int freq[256]; freq = {0};

Solution

1. Step 1: Check correct array initialization syntax in C

   int freq[256] = {0}; uses correct syntax to initialize all 256 elements to zero using brace initialization.

2. Step 2: Analyze other options for errors

   int freq[26]; for(int i=0; i<26; i++) freq[i] = -1; does not initialize all elements and sets to -1 incorrectly. int freq[128]; memset(freq, 1, sizeof(freq)); uses memset with 1 which sets bytes to 1, not zero. int freq[256]; freq = {0}; tries to assign array which is invalid in C.

3. Final Answer:

   int freq[256] = {0}; -> Option A

4. Quick Check:

   Correct zero initialization = int freq[256] = {0}; [OK]

Hint: Use brace initialization to zero arrays in C [OK]

Common Mistakes:

• Using memset with wrong value
• Trying to assign arrays directly
• Not initializing all elements

3. What will be the output of the following C code snippet for Minimum Window Substring?

char s[] = "ADOBECODEBANC";
char t[] = "ABC";
// Assume function minWindow returns the minimum window substring
char* result = minWindow(s, t);
printf("%s", result);

Assuming minWindow is correctly implemented, what is printed?

medium

A. CODEBA

B. ADOBEC

C. BANC

D. DOBECODEBA

Solution

1. Step 1: Understand the input strings

   String s is "ADOBECODEBANC" and t is "ABC". We want the smallest substring of s containing A, B, and C.

2. Step 2: Identify the minimum window substring

   The substring "BANC" is the smallest substring containing all characters A, B, and C.

3. Final Answer:

   BANC -> Option C

4. Quick Check:

   Minimum window substring for "ABC" in s = "BANC" [OK]

Hint: Remember classic example: "BANC" is minimum window for "ABC" [OK]

Common Mistakes:

• Choosing first substring containing all chars instead of minimum
• Confusing order of characters
• Ignoring repeated characters

4. Consider this buggy C code snippet for Minimum Window Substring:

int left = 0, right = 0;
int count = 0;
while (right < strlen(s)) {
    if (freq[s[right]] > 0) count++;
    freq[s[right]]--;
    right++;
    while (count == t_len) {
        if (right - left < min_len) {
            min_len = right - left;
            start = left;
        }
        freq[s[left]]++;
        if (freq[s[left]] > 0) count--;
        left++;
    }
}
// Returns substring from start with length min_len

What is the main bug in this code?

medium

A. Using strlen(s) inside the loop condition causes repeated length calculation

B. Incorrect update of count when moving left pointer

C. The inner while condition should be count >= t_len

D. freq array is not initialized before use

Solution

1. Step 1: Analyze freq array usage

   The freq array is decremented and incremented but not initialized, so it contains garbage values causing incorrect logic.

2. Step 2: Check other options

   Using strlen(s) inside the loop condition causes repeated length calculation is inefficient but not a bug. Incorrect update of count when moving left pointer logic is correct for count update. The inner while condition should be count >= t_len is incorrect because count == t_len is the correct condition.

3. Final Answer:

   freq array is not initialized before use -> Option D

4. Quick Check:

   freq must be zero-initialized before use [OK]

Hint: Always initialize frequency arrays before use [OK]

Common Mistakes:

• Ignoring initialization of freq array
• Misunderstanding count update logic
• Confusing loop conditions

5. You want to find the minimum window substring of s = "aabbccdd" that contains all characters of t = "abc". Which approach correctly handles repeated characters in s and t to find the minimum window?

hard

A. Count unique characters in t and find first substring in s containing those unique chars

B. Use two frequency arrays: one for t counts and one for current window counts, then expand and contract window accordingly

C. Use a single frequency array for t and move right pointer until all chars found, then stop

D. Sort s and t and find common characters sequentially

Solution

1. Step 1: Understand the need for frequency tracking

   Since t can have repeated characters, we must track how many times each character is needed and how many times it appears in the current window.

2. Step 2: Use two frequency arrays and sliding window

   One array stores counts of characters in t, another tracks counts in the current window. Expand right pointer to include chars, contract left pointer to minimize window while keeping all required chars.

3. Final Answer:

   Use two frequency arrays: one for t counts and one for current window counts, then expand and contract window accordingly -> Option B

4. Quick Check:

   Two freq arrays + sliding window = correct approach [OK]

Hint: Track needed and current counts separately for repeated chars [OK]

Common Mistakes:

• Ignoring repeated characters in t
• Using only unique character counts
• Stopping window expansion too early