Find the Shortest Substring Covering Required Characters
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Find the shortest contiguous substring of `text` that contains every character required by `needed`, respecting how many times each character occurs. Return that substring, or the empty string `""` if no qualifying substring exists.
Uppercase and lowercase letters are different characters. Extra characters may occur inside the returned substring. Inputs guarantee that the returned answer is unique.
### Examples
**Example 1**
```text
Input: text = "zABACx", needed = "AABC"
Output: "ABAC"
```
This window contains two `A`s, one `B`, and one `C`. No shorter substring can contain all four required occurrences.
**Example 2**
```text
Input: text = "Bb", needed = "BB"
Output: ""
```
There is only one uppercase `B`. The lowercase `b` cannot supply the second required occurrence.
### Constraints
- `1 <= text.length <= 10^5`
- `1 <= needed.length <= 10^5`
- Both strings contain uppercase or lowercase English letters only.
- Every supplied input has a unique answer under the stated rules.
### Optional Follow-up
Can you achieve `O(text.length + needed.length)` running time?
Overview: Find the unique shortest substring covering every required character occurrence, respecting repeated letters and case, or return an empty string.
