Skip to main content
Ace Hired
All coding problems

Minimum Window Substring

Mediumsliding windowSliding window with character-count maps and a satisfied-need countersliding-windowstringshash-map

Maintained by Vikas D, software engineer

You are given a source string `s` and a target string `t`. A valid window is any contiguous slice of `s` that holds at least as many of each character as `t` requires. If `t` has two copies of a character, the window must contain at least two of that character as well.

Among all valid windows, you want the one with the fewest characters. The window only needs to cover `t`; it may contain extra characters that `t` never asks for, and those extras do not disqualify it.

Return the actual substring, not its length or its bounds. When `s` cannot cover everything `t` needs, return the empty string. The guarantee in interviews is usually that the answer is unique, but the shortest-window rule already decides ties by length.

The target is a single linear pass: the work should scale with `|s| + |t|`, not with the number of possible windows.

Examples

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Reading left to right, the first window that covers A, B, and C runs from the first A to the C, but it is long. The window "BANC" near the end also covers all three and is shorter, so it wins.

Input: s = "AABC", t = "ABC"
Output: "ABC"

The leading extra A is not needed, so the optimal window drops it and lands on the trailing "ABC", which covers one A, one B, and one C with nothing to spare.

Input: s = "a", t = "aa"
Output: ""

The target wants two copies of 'a' but `s` only offers one, so no window can ever cover `t` and the answer is the empty string.

Constraints

  • 1 <= s.length, t.length <= 10^5
  • Both strings consist of uppercase and lowercase English letters, and case matters: 'a' and 'A' are different
  • The result is the shortest covering substring of `s`, or "" when none exists
  • A solution running in O(|s| + |t|) time is expected

Visible test cases

  • minWindow("ADOBECODEBANC", "ABC") == "BANC"
  • minWindow("a", "a") == "a"
  • minWindow("a", "aa") == ""
  • minWindow("ab", "b") == "b"
  • minWindow("AABC", "ABC") == "ABC"
  • minWindow("xyz", "z") == "z"
  • minWindow("cabwefgewcwaefgcf", "cae") == "cwae"

Hints

Hint 1

Counts, not just presence, drive this problem. Build a frequency table of what `t` needs so you can tell when a window has enough of every character, duplicates included.

Hint 2

Grow a window by moving its right edge forward and adding each new character. Once the window covers all of `t`, stop growing and instead try to shrink it from the left while it still stays valid.

Hint 3

Track how many distinct required characters are currently satisfied rather than rescanning the whole table each step. A character becomes satisfied the moment its in-window count reaches its required count, and unsatisfied the moment a shrink drops it below.

Loading the editor...

Approaches

Brute force over every window

Time O(n^2) windows times the cost of each coverage check, which is far above the linear target · Space O(k) for the count tables, where k is the number of distinct characters

Try every start and end position, and for each candidate substring check whether it covers all the character counts that `t` demands.

  1. For each start index i, extend an end index j across the rest of `s`.
  2. Maintain a count of characters seen since i and compare it against the required counts from `t`.
  3. When the slice from i to j first covers `t`, record its length if it beats the best so far and stop extending this start.
  4. After scanning all starts, return the shortest covering slice, or the empty string if none covered `t`.

Optimal sliding window with a need counter

Time O(|s| + |t|), since each character of `s` enters and leaves the window at most once · Space O(k) for the need and window-count maps, bounded by the size of the alphabet

Keep one window that expands on the right and contracts on the left. Track how many required characters are fully satisfied so you know in constant time whether the window currently covers `t`.

  1. Build `need`, a map from each character of `t` to how many copies are required, and set `required` to the number of distinct required characters.
  2. Walk the right edge across `s`, incrementing the window's count for each character. When a character's window count exactly reaches its required count, increase a `formed` counter.
  3. While `formed` equals `required`, the window covers `t`: record it if it is the shortest seen, then drop the leftmost character, decrement its count, and if that pushes a required character below its needed count, decrease `formed`.
  4. Advance the left edge after each drop, then continue expanding the right edge.
  5. Return the shortest recorded window, or the empty string if no window ever covered `t`.

Common mistakes

  • Tracking only whether a character is present instead of how many copies are needed. The "a" versus "aa" case fails the moment duplicates are ignored.
  • Recounting the entire need table on every step to decide coverage, which quietly turns the loop quadratic and misses the linear bound.
  • Using `formed` increments on every count bump rather than only when a character's window count first hits its required count, which inflates the counter and reports false coverage.
  • Forgetting to record the best window before shrinking, or shrinking past the point where the window is still valid, so the returned slice is too long or no longer covers `t`.
  • Treating uppercase and lowercase as the same character, which breaks inputs that mix cases.
  • Returning a length or index pair when the prompt asks for the substring itself.

Follow-up variations

  • Return the start and end indices of the minimum window instead of the substring, which removes the slicing step but needs careful bound tracking.
  • Find the minimum window that contains every character of `t` in the same order they appear in `t`, turning this into a subsequence problem rather than a multiset problem.
  • Support a very large or unicode alphabet where a fixed-size array is no longer practical and the count maps must stay sparse.
  • Handle a streaming `s` where characters arrive one at a time and you must report the best window found so far without holding the whole string in memory.
  • Return all minimum-length windows when several tie, rather than just one.

Recommended problems

Build the rest of your prep