Minimum Window Substring in DSA Python - 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 from another string changes as the input grows.

How does the running time increase when the input strings get longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from collections import Counter

def min_window(s: str, t: str) -> str:
    need = Counter(t)
    missing = len(t)
    left = start = end = 0

    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1

        while missing == 0:
            if end == 0 or right - left + 1 < end - start:
                start, end = left, right + 1
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1

    return s[start:end]
    

This code finds the smallest substring in s that contains all characters of t.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The main 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 right pointer and once when moving the left pointer.

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 character 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 to find the minimum window grows linearly with the size of both input strings s and t.

Common Mistake

[X] Wrong: "The nested while loop makes this algorithm quadratic, so it must be O(n²)."

[OK] Correct: Although there is a nested loop, each character is visited at most twice in total, so the total work is still linear, not quadratic.

Interview Connect

Understanding this sliding window approach and its linear time complexity shows you can handle problems that require careful pointer movement and counting, a valuable skill in many coding challenges.

Self-Check

"What if the input string t contains many repeated characters? How would that affect the time complexity?"