CoreCoding

Built for depth, not noise.

Back to DSA track

Minimum Window Substring

Find the smallest substring of s that contains every character of t, including duplicate counts.

HARD

Problem intuition

The brute-force version tries every possible substring and checks whether it covers the target counts.
The optimal solution grows the window until all requirements are met, then shrinks from the left to make the valid window as small as possible.

Solution

The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.

Solution 1

Check every substring

Generate every substring and test whether it covers all required characters.
This is straightforward, but very expensive.
▸
Time complexity: O(n^3)
- you generate many substrings and repeatedly rescan them to verify whether they cover the target.
▸
Space complexity: O(charset)
- the frequency map stores counts for the characters needed to validate a candidate window.

Solution 2

Sliding window with satisfied requirements

Track target frequencies as the window expands.
Once the window is valid, shrink greedily to capture the smallest valid answer.
▸
Time complexity: O(n)
- the window expands and shrinks with forward-only pointer movement while each character is processed a constant number of times.
▸
Space complexity: O(charset)
- the need and window maps store counts keyed by the characters involved in the strings.