/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 duplicate occurrences). If no such substring exists, return the 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=abcdefg, target_string=gfed

Output: defg

Explanation: The substring defg contains all characters from target_string.

Example 3

Input: source_string=abc, target_string=abcd

Output: ''

Explanation: Not all characters from target_string are 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='AABBC', target_string='ABC'

Expected: 'BBC'

Case 2

Input: source_string='qwertyqwerty', target_string='tyq'

Expected: 'tyq'

Case 3

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

Expected: ''

Case 4

Input: source_string='aabbccdd', target_string='bbcc'

Expected: 'bbcc'

Case 5

Input: source_string='zxyxzyx', target_string='xyzx'

Expected: 'xzyx'