Implement Minimum Window Substring

MediumPython

Problem

Lyra Care may need to locate the smallest portion of a member message that contains every character from a required search pattern. Given a text string and a pattern string, return the shortest contiguous substring of text that contains all characters in pattern, including duplicate occurrences.

Character matching is case-sensitive, spaces and punctuation are valid characters, and the returned substring must preserve the original text exactly. If multiple shortest substrings exist, return the one with the smallest starting index. Return an empty string when no valid substring exists.

Formal Specification

Implement min_covering_window(text, pattern).

Input: two strings, text and pattern.
Output: the shortest contiguous substring of text containing every character in pattern with at least the required frequency.
The input strings contain printable ASCII characters.

Constraints

1 <= len(text) <= 100,000
1 <= len(pattern) <= 100,000
Both strings contain printable ASCII characters
Matching is case-sensitive

Function Signature

def min_covering_window(text, pattern):

Formal Specification

Implement min_covering_window(text, pattern).

Input: two strings, text and pattern.
Output: the shortest contiguous substring of text containing every character in pattern with at least the required frequency.
The input strings contain printable ASCII characters.