26. Minimum Window Substring

You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:

A large search, security, or content filtering platform scans text streams to find the smallest segment that satisfies a set of required tokens. Examples include:

• finding the smallest log snippet that contains all required error codes
• extracting the shortest text span that includes all compliance keywords
• locating the minimum-length window that includes specific characters for query rewriting
• detecting the smallest session fragment containing required event markers

The platform receives:

• a source string s representing the full log or text stream
• a target string t representing required characters with frequency requirements

The platform needs the shortest contiguous substring of s that contains every character in t, including duplicates.

This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.

Your Task

Given two strings s and t, 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 an empty string "".

Input Format

• s: a string representing the source text
• t: a string representing required characters

Output Format

• A string representing the minimum window in s that contains all characters of t
• Return "" if no valid window exists

Examples

Constraints

• 1 <= s.length <= 200,000
• 1 <= t.length <= 100,000
• s and t consist of uppercase and lowercase English letters