Shrink-and-Grow Substring Search
Problem Description
Given two strings `source` and `pattern`, find the minimum-length contiguous substring of `source` that contains all the characters of `pattern` (with multiplicity). Return that substring. If no such substring exists, return an empty string `""`.
If there are multiple substrings of the same minimum length, return the one that appears first (leftmost).
**Example 1:**
```
Input: source = "DOORSTEP", pattern = "ORS"
Output: "OORS"
Explanation: "OORS" (indices 1–4) contains 'O','O','R','S' and covers all of 'O','R','S'. Length 4 is minimal.
```
**Example 2:**
```
Input: source = "jumpstart", pattern = "art"
Output: "art"
Explanation: "art" appears directly at the end of "jumpstart", covering 'a','r','t' with length 3.
```
**Example 3:**
```
Input: source = "xyz", pattern = "abc"
Output: ""
Explanation: 'a','b','c' do not appear in source at all.
```
Constraints
- 1 <= source.length <= 10^5
- 1 <= pattern.length <= 10^5
- source and pattern consist of uppercase and lowercase English letters
Follow-up
What if you must return all minimum-length windows (not just the first), still in O(n) time?
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.