{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Minimum Window Substring – Solution & Complexity

Interview solutions
/
Minimum Window Substring

Solution Walkthrough

1. Translate the requirement into counts

  • A window is valid only if it contains each character from t at least as many times as t requires.
  • That means the problem is not about distinct letters alone; duplicates like the second a in t = "aba" matter too.

2. Brute-force baseline

  • Enumerate every substring of s and count its characters to see whether it covers t.
  • Even with small optimizations, that approach becomes at least quadratic and is too slow for long strings.

3. Use a variable-size sliding window

  • Keep a frequency table for t, a frequency table for the current window, and a counter tracking how many required character types are currently satisfied.
  • Expand the right edge until the window becomes valid. Then shrink the left edge while the window stays valid so you can record the shortest valid window ending at this right position.
  • Each pointer only moves forward, which keeps the scan linear.

4. Final solution (all languages)

Track the smallest valid window while growing and shrinking the same sliding range exactly once.

def min_window(s: str, t: str) -> str:
    if len(t) > len(s):
        return ""

    need = {}
    for char in t:
        need[char] = need.get(char, 0) + 1

    have = {}
    formed = 0
    required = len(need)
    best_start = 0
    best_length = len(s) + 1
    left = 0

    for right, char in enumerate(s):
        have[char] = have.get(char, 0) + 1
        if char in need and have[char] == need[char]:
            formed += 1

        while formed == required:
            window_length = right - left + 1
            if window_length < best_length:
                best_length = window_length
                best_start = left

            left_char = s[left]
            have[left_char] -= 1
            if left_char in need and have[left_char] < need[left_char]:
                formed -= 1
            left += 1

    if best_length == len(s) + 1:
        return ""
    return s[best_start:best_start + best_length]

5. Common pitfalls

  • Forgetting multiplicity: t = "AABC" needs two A characters, not just presence.
  • Shrinking the window before recording the current best valid answer.
  • Treating character types satisfied as the total number of matched characters; the two counters mean different things.

FAQ

See also

Practice Minimum Window Substring online (run code in the browser)Longest Substring Without Repeating Characters solution (medium)First Unique Character in a String solution (easy)Roman to Integer solution (easy)Valid Anagram solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?