Shortest Substring Containing Every Character of a Pattern
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
Given two strings `s` and `t`, return the shortest contiguous substring of `s` that contains every character of `t`, counting repeats: if a character appears `m` times in `t`, the substring must contain it at least `m` times. Characters are case-sensitive. If no such substring exists, return the empty string.
### Function Signature
```python
def min_window(s: str, t: str) -> str:
```
### Rules
- The substring may contain characters that do not occur in `t`, and extra copies of characters that do.
- If several substrings share the minimum length, return the one that starts at the smallest index of `s`.
- Return `""` when `s` has no qualifying substring, for example when `t` is longer than `s`.
### Constraints
- `1 <= len(s) <= 10^5`
- `1 <= len(t) <= 10^5`
- `s` and `t` consist of uppercase and lowercase English letters.
### Examples
**Example 1**
- Input: `s = "XAYBZAXB"`, `t = "ABX"`
- Output: `"AXB"`
- Explanation: `"XAYB"` and `"BZAX"` also contain `A`, `B` and `X`, but they have length 4. `"AXB"`, starting at index 5, has length 3, and no other substring of length 3 qualifies.
**Example 2**
- Input: `s = "cabwba"`, `t = "ab"`
- Output: `"ab"`
- Explanation: `"ab"` (starting at index 1) and `"ba"` (starting at index 4) both have length 2; the one that starts earlier is returned.
**Example 3**
- Input: `s = "Aa"`, `t = "AA"`
- Output: `""`
- Explanation: `t` needs two uppercase `A` characters, `s` has only one, and the lowercase `a` does not count.
Overview: Return the shortest substring of a string that contains every character of a pattern with matching multiplicity, case-sensitively, choosing the leftmost substring on ties and an empty string when none exists. Tests efficient substring search and careful character-count bookkeeping.
Read the full LinkedIn Software Engineer interview experience this question came from