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.