Min Window Substring

Python data engineering interview problem. Difficulty: intermediate. Pattern: Sliding Window. About 14 minutes. Part of the Pro drill bank.

Smallest window in s covering all characters of t. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

A search service has a long text and a short set of required characters. It needs the smallest continuous piece of the text that contains every required character, including repeated requirements. Return the shortest substring of s that contains all characters from t with the required counts. Return an empty string when no such window exists. Write the function min_window(s: str, t: str) -> str. For 'ADOBECODEBANC' and 'ABC', the smallest covering window is 'BANC'. The starter file already has the function name and the harness print lines. Keep them, and fill only the function body.

Requirements

• Count repeated characters in t, not only distinct characters.
• Expand until a window is valid, then shrink it while it stays valid.
• Return the substring itself, or '' if no window covers t.

Constraints

• The matching is case-sensitive, so A and a are different.
• The return type is str, and the answer must be a contiguous part of s.

Examples

Input: min_window('ADOBECODEBANC', 'ABC') Output: BANC BANC is the shortest cover.

Topics: lakebench, python, window, coverage.

More Python interview questions · All interview problems · Learn data engineering