Smallest Covering Substring | Dataford Interview Questions

The SIXT app receives a user search query and a set of required characters from a matching rule. Find the shortest contiguous substring of source that contains every character in target, including duplicate occurrences. Matching is case-sensitive.

Return any shortest valid window. If no valid window exists, return an empty string.

Formal Specification

Implement min_window(source, target):

source: a string containing the searchable text.
target: a non-empty string containing the required characters.
Return: the shortest substring of source that contains each character in target with at least the required frequency.

Use a sliding-window approach suitable for large search queries.

Constraints

1 <= len(source) <= 10^5
1 <= len(target) <= 10^4
Characters may include letters, digits, spaces, and punctuation
Matching is case-sensitive
If multiple shortest windows exist, return any one

Function Signature

def min_window(source, target):

Your question is Smallest Covering Substring. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem