Minimum Window Substring in DSA C - Time & Space Complexity

Time Complexity: Minimum Window Substring

O(n + m)

Understanding Time Complexity

We want to understand how the time needed to find the smallest substring containing all characters of another string grows as the input size increases.

How does the algorithm's work change when the input strings get longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int minWindow(char* s, char* t) {
    int need[128] = {0}, window[128] = {0};
    int left = 0, right = 0, valid = 0;
    int start = 0, len = 0x3f3f3f3f;
    
    for (int i = 0; t[i]; i++) need[(unsigned char)t[i]]++;
    int total = 0;
    for (int i = 0; i < 128; i++) {
        if (need[i] > 0) total++;
    }
    
    while (s[right]) {
        char c = s[right];
        right++;
        if (need[(unsigned char)c] > 0) {
            window[(unsigned char)c]++;
            if (window[(unsigned char)c] == need[(unsigned char)c]) valid++;
        }
        while (valid == total) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            char d = s[left];
            left++;
            if (need[(unsigned char)d] > 0) {
                if (window[(unsigned char)d] == need[(unsigned char)d]) valid--;
                window[(unsigned char)d]--;
            }
        }
    }
    return len == 0x3f3f3f3f ? 0 : len;
}

This code finds the smallest substring in s that contains all characters of t using a sliding window approach.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer while loop moves the right pointer through string s, and the inner while loop moves the left pointer to shrink the window.
• How many times: Each character in s is visited at most twice, once when expanding the window and once when shrinking it.

How Execution Grows With Input

As the input string s grows, the number of operations grows roughly in proportion to its length because each character is processed a limited number of times.

Input Size (n)	Approx. Operations
10	About 20 (each char visited twice)
100	About 200
1000	About 2000

Pattern observation: The operations grow linearly with input size, doubling roughly when input size doubles.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows linearly with the size of both input strings, processing each character a limited number of times.

Common Mistake

[X] Wrong: "The nested while loops make this algorithm quadratic (O(n²)) because of the inner loop inside the outer loop."

[OK] Correct: Each character is visited at most twice, so the inner loop does not run fully for every outer loop iteration, keeping the total operations linear.

Interview Connect

Understanding this sliding window technique and its linear time complexity helps you solve many substring and array problems efficiently, a valuable skill in coding interviews.

Self-Check

"What if we changed the input to allow Unicode characters beyond ASCII? How would the time complexity change?"