O(n) String Manipulation

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is O(n) String Manipulation. 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

A Siemens Teamcenter integration receives a long text stream and must locate the shortest contiguous segment containing every character from a required token. Return the minimum-length window, preserving the original character casing and order.

Characters are matched exactly, so uppercase and lowercase letters are different. If a required character appears multiple times, the window must contain at least the same number of occurrences. If no valid window exists, return an empty string.

Formal Specification

Implement min_cover_window(source, required).

Input: Two strings, source and required.
Output: The shortest contiguous substring of source containing all characters in required, including duplicate occurrences.
If multiple windows have the same minimum length, return the one with the smallest starting index.

Constraints

0 <= len(source), len(required) <= 10^5
Inputs contain printable ASCII characters
Character matching is case-sensitive
Duplicate characters in required must be matched with equal or greater frequency
Return an empty string when required is empty or no valid window exists

Function Signature

def min_cover_window(source, required):

Your solutionPython 3

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

Run your code to see test output