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 function when called with s = "ADOBECODEBANC" and t = "ABC"?

DSA C

char* minWindow(char* s, char* t) {
    int need[128] = {0}, have[128] = {0};
    int required = 0, formed = 0;
    int left = 0, right = 0, start = 0, min_len = 100000;
    for (int i = 0; t[i]; i++) {
        if (need[t[i]] == 0) required++;
        need[t[i]]++;
    }
    while (s[right]) {
        char c = s[right];
        have[c]++;
        if (have[c] == need[c]) formed++;
        while (left <= right && formed == required) {
            if (right - left + 1 < min_len) {
                min_len = right - left + 1;
                start = left;
            }
            char d = s[left];
            have[d]--;
            if (have[d] < need[d]) formed--;
            left++;
        }
        right++;
    }
    if (min_len == 100000) return "";
    char* res = (char*)malloc(min_len + 1);
    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);
    free(result);
    return 0;
}

A "BANC"

B "ADOBEC"

C "CODEBA"

D "DOBECODEBA"

💡 Hint

Think about the smallest substring containing all characters of t.

The minimum window substring containing all characters 'A', 'B', and 'C' in s is "BANC".

🧠 Conceptual

intermediate

Understanding the Sliding Window Technique

In the Minimum Window Substring problem, why do we move the left pointer forward after finding a valid window?

A To reset the window and start searching from scratch.

B To increase the window size to include more characters.

C To try to find a smaller valid window by removing unnecessary characters from the left.

D To skip characters that are not in the target string t.

💡 Hint

Think about minimizing the window size while keeping it valid.

After finding a valid window, moving the left pointer forward helps to shrink the window and find the smallest possible valid substring.

🔧 Debug

advanced

Identify the Bug in Minimum Window Substring Code

What error will occur when running this code snippet for Minimum Window Substring?

DSA C

char* minWindow(char* s, char* t) {
    int need[128] = {0}, have[128] = {0};
    int required = 0, formed = 0;
    int left = 0, right = 0, start = 0, min_len = 100000;
    for (int i = 0; t[i]; i++) {
        need[t[i]]++;
        required++;
    }
    while (s[right]) {
        char c = s[right];
        have[c]++;
        if (have[c] == need[c]) formed++;
        while (left <= right && formed == required) {
            if (right - left + 1 < min_len) {
                min_len = right - left + 1;
                start = left;
            }
            char d = s[left];
            have[d]--;
            if (have[d] < need[d]) formed--;
            left++;
        }
        right++;
    }
    if (min_len == 100000) return "";
    char* res = (char*)malloc(min_len + 1);
    strncpy(res, s + start, min_len);
    res[min_len] = '\0';
    return res;
}

A Memory leak due to missing free() call for allocated memory.

B The variable 'required' counts total characters including duplicates, causing incorrect formed count.

C Segmentation fault due to accessing s[right] without checking null terminator.

D Syntax error because of missing semicolon after variable declarations.

💡 Hint

Check how 'required' is calculated and used.

The code increments 'required' for every character in t, including duplicates, but 'formed' counts unique characters matched. This mismatch causes the window to never be recognized as valid.

🚀 Application

advanced

Minimum Window Substring with Unicode Characters

How would you modify the Minimum Window Substring algorithm to handle Unicode characters beyond ASCII?

A Use a hash map or dictionary to count characters instead of fixed-size arrays.

B Increase the size of the fixed array to 256 to cover extended ASCII.

C Convert all characters to lowercase ASCII before processing.

D Ignore characters outside ASCII range to simplify the problem.

💡 Hint

Think about character sets larger than 128.

Unicode characters require dynamic data structures like hash maps to count frequencies, as fixed arrays for ASCII are insufficient.

🧠 Conceptual

expert

Time Complexity of Minimum Window Substring Algorithm

What is the time complexity of the optimal Minimum Window Substring algorithm using the sliding window technique?

A O(m^2), where m is length of t

B O(n * m), where n is length of s and m is length of t

C O(n^2), where n is length of s

D O(n + m), where n is length of s and m is length of t

💡 Hint

Consider how many times each pointer moves.

Each character in s is visited at most twice by the two pointers, and t is processed once, resulting in O(n + m) time.