šŸ”— LeetCodešŸ”— Neetcode

Minimum Window Substring

Hardā˜… Premiumsliding windowMetaAmazonGoogleAirbnb

Given two strings s and t of lengths m and n respectively, return the **minimum window substring** of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".


The answer is guaranteed to be unique.

Examples

Input:s = "ADOBECODEBANC", t = "ABC"
Output:"BANC"
Explanation:The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Input:s = "a", t = "a"
Output:"a"
Explanation:The entire string s is the minimum window.
Input:s = "a", t = "aa"
Output:""
Explanation:Both 'a's from t must be included. Since s only has one 'a', return empty string.

Constraints

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 10^5
  • s and t consist of uppercase and lowercase English letters

šŸ’” Hints

Hint 1

Use a frequency map for characters in t.

Hint 2

Expand window right until all characters are covered, then shrink from left to minimize.

Hint 3

Track how many characters are 'satisfied' to know when the window is valid.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Linear
Algorithmic Approach

Build frequency map of t. Expand window right, counting satisfied chars. When all satisfied, shrink from left to find minimum. Track best result.

Time ComplexityO(m + n)
Why:

Both right and left pointers traverse string s of length m at most once, and initial target frequency map builds in O(n).

Space ComplexityO(m + n)
Why:

Frequency hash maps store counts of characters in target t and current window in s.

Big-O Growth CurveLinear (O(N))
Execution time scales directly in proportion to the input size.

šŸŒ Real-World Use Cases

Search EnginesSnippet extraction

Finding the shortest text snippet in a document that contains all search query terms ā€” directly uses min window logic.

ā˜… Premium Challenge

Minimum Window Substring is classified as a premium problem.

Client-Side Architecture Preview (Phase 3 Sprint 3)
This gating is an honest client-side architecture preview. True secure server entitlements, user database roles, and payment verification will be introduced in Phase 4 with the PostgreSQL backend. There is no fake checkout or simulated payment processing.
Difficulty: HardPattern: sliding-windowCompanies: Meta, Amazon, Google