Minimum Window Substring in DSA C - Build from Scratch

Minimum Window Substring

📖 Scenario: You are working on a text processing tool that needs to find the smallest part of a text containing all required characters.Imagine you have a long string and a set of characters you want to find inside it. Your task is to find the shortest substring that contains all these characters at least once.

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

📋 What You'll Learn

Create two input strings: s and t with exact values

Create an integer array char_count to count characters needed

Implement the sliding window technique using two pointers start and end

Find and print the minimum window substring that contains all characters of t

If no such window exists, print an empty string

💡 Why This Matters

🌍 Real World

Finding minimum window substrings is useful in text search, DNA sequence analysis, and data filtering where you want the smallest segment containing all required elements.

💼 Career

This problem is common in coding interviews and helps develop skills in string manipulation, hash maps, and two-pointer techniques used in software development.

1

Create input strings

Create two strings called s and t with these exact values: s = "ADOBECODEBANC" and t = "ABC".

DSA C

# Create strings s and t with given values
// Your code here

Hint

Use char s[] = "ADOBECODEBANC"; and char t[] = "ABC"; to create the strings.

2

Initialize character count array

Create an integer array called char_count of size 256 and initialize all elements to 0. Then, fill char_count with the frequency of each character in t using a for loop with variable i.

DSA C

#include 
#include 

char s[] = "ADOBECODEBANC";
char t[] = "ABC";

// Create and initialize char_count array
// Your code here

Hint

Use a loop to count characters in t and store counts in char_count.

3

Implement sliding window to find minimum substring

Implement the sliding window using two integer variables start and end initialized to 0. Use an integer count initialized to the length of t. Use a while loop with condition end < strlen(s). Inside the loop, if char_count[s[end]] > 0, decrement count. Decrement char_count[s[end]] and increment end. When count == 0, move start forward while char_count[s[start]] < 0, incrementing char_count[s[start]] and start. Track the minimum window length and start index.

DSA C

#include 
#include 

char s[] = "ADOBECODEBANC";
char t[] = "ABC";

int char_count[256] = {0};

for (int i = 0; t[i] != '\0'; i++) {
    char_count[(unsigned char)t[i]]++;
}

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

Hint

Use two pointers start and end to slide over s. Adjust counts and track minimum window.

4

Print the minimum window substring

Print the minimum window substring using printf. If min_len is greater than the length of s, print an empty string "". Otherwise, print characters from min_start to min_start + min_len - 1.

DSA C

#include 
#include 

char s[] = "ADOBECODEBANC";
char t[] = "ABC";

int char_count[256] = {0};

for (int i = 0; t[i] != '\0'; i++) {
    char_count[(unsigned char)t[i]]++;
}

int start = 0, end = 0, min_start = 0, min_len = 1000000;
int count = strlen(t);

while (end  0) {
        count--;
    }
    char_count[(unsigned char)s[end]]--;
    end++;

    while (count == 0) {
        if (end - start  0) {
            count++;
        }
        start++;
    }
}

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

Hint

Print the substring from min_start to min_start + min_len - 1. If no valid window, print empty quotes.