Katkat
Back

Find the Minimum Window Containing a Multiset of Characters

ByteDanceSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to use the two-pointer sliding window technique combined with a frequency map to identify the smallest valid substring efficiently.

Problem Statement

Given two strings s and t, return the smallest contiguous substring of s that contains all the characters in t (including duplicates). If there are multiple substrings with the same minimum length, return the one that starts at the smallest index. If no such substring exists, return an empty string.

Function Signature

def min_window(s: str, t: str) -> str:

Constraints

  • 0 <= len(s), len(t) <= 10^5
  • s and t consist of English letters (case-sensitive).
  • The time complexity should be O(len(s) + len(t)).

Examples

Example 1:

  • Input: s = "ADOBECODEBANC", t = "ABC"
  • Output: "BANC"
  • Explanation: The minimum window is "BANC", which contains 'A', 'B', and 'C'.

Example 2:

  • Input: s = "a", t = "aa"
  • Output: ""
  • Explanation: The target requires two 'a's, but s only has one.

Edge Cases

  • If t is empty, return an empty string.
  • If len(s) < len(t), return an empty string.
  • If no window is found, return an empty string.

Hints

Hint 1

Use a hash map to count the frequencies of characters required in `t`.

Hint 2

Maintain a sliding window defined by two pointers `left` and `right`, expanding `right` to include characters and shrinking `left` to optimize the window once all requirements are met.

Hint 3

Track the count of 'satisfied' characters (where the window count matches the requirement count) to avoid scanning the entire map on every iteration.

Follow-up questions

  • How would you modify your solution if the input strings contained Unicode characters instead of just English letters?
  • If the input `s` is extremely large and stored on disk, how would you approach the problem to minimize memory usage?
  • Can you adapt this algorithm to find the longest substring that contains at most K distinct characters?