Smallest Covering Substring

HardPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Smallest Covering Substring. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output