/76. Minimum Window Substring

76. Minimum Window Substring

Hard

Hash Table47.1% acceptance

Given two strings source_string and target_string, return the shortest contiguous substring of source_string that contains all characters from target_string (including duplicates). If no such substring exists, return an empty string. The answer is guaranteed to be unique for each input.

Example 1

Input: source_string=XYZZYZX, target_string=ZYZ

Output: ZZYZ

Explanation: The substring ZZYZ contains two Zs and one Y, which matches target_string.

Example 2

Input: source_string=abcdef, target_string=fba

Output: abcf

Explanation: The substring abcf contains a, b, and f.

Example 3

Input: source_string=aabbcc, target_string=abcabc

Output: aabbcc

Explanation: The entire string is needed to cover all characters with duplicates.

Example 4

Input: source_string=abc, target_string=d

Output: ''

Explanation: Character d is not present in source_string.

Constraints

1 <= len(source_string) <= 10⁵
1 <= len(target_string) <= 10⁵
source_string and target_string consist of uppercase and lowercase English letters

Python (current runtime)

Case 1

Input: source_string='QWERTYQWER', target_string='QWE'

Expected: 'QWE'

Case 2

Input: source_string='mnoonm', target_string='omm'

Expected: 'onm'

Case 3

Input: source_string='xyz', target_string='xyz'

Expected: 'xyz'

Case 4

Input: source_string='abcdabcd', target_string='dcba'

Expected: 'dcba'

Case 5

Input: source_string='aabb', target_string='bbb'

Expected: ''