What is the time and space complexity of Minimum Window Substring?

Time complexity: O(n + m). Space complexity: O(n + m).

Minimum Window Substring

Hard

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Minimum Window Substring

Approach

Build a frequency map for t to know what characters are required. Expand the window rightward, tracking how many unique characters have met their required frequency (formed counter). Once all are met, shrink from the left to find the minimum valid window, updating the answer each time.

Complexity Analysis

Time: O(n + m)
Space: O(n + m)

Pattern

Sliding Window (Variable Size + Frequency)

Why It Works

The formed counter tracks how many of t's unique characters are fully satisfied. Expanding right can only increase or maintain formed, while shrinking left can only decrease or maintain it. This monotonic behavior ensures we find the global minimum window efficiently.

Updated Feb 2026