Shortest Substring Containing All Pattern Characters with Repeats
Company: Lyft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a string `s` and a pattern `t`, return the shortest contiguous substring of `s` that contains every character of `t`, counting repeats: if a character appears `c` times in `t`, the substring must contain it at least `c` times. After coding, be ready to walk through the test cases you would use and to state the time and space complexity of your solution.
### Function Signature
```python
def shortest_covering_substring(s: str, t: str) -> str:
```
### Rules
- Matching is case-sensitive: `'a'` and `'A'` are different characters.
- The substring may contain characters that are not in `t`, and more copies of a character than `t` requires.
- If several qualifying substrings have the minimum length, return the one that starts at the smallest index.
- If no substring of `s` qualifies (for example, when `t` is longer than `s`), return the empty string `""`.
### Constraints
- `1 <= len(s) <= 10^5`
- `1 <= len(t) <= 10^5`
- `s` and `t` consist of uppercase and lowercase English letters.
### Examples
**Example 1**
```text
Input: s = "AXXBXCXXAB", t = "ABC"
Output: "CXXAB"
```
`"CXXAB"` (indices `5` to `9`) contains `A`, `B` and `C`. The substrings `"AXXBXC"` (indices `0` to `5`) and `"BXCXXA"` (indices `3` to `8`) also contain all three, but they have length `6`, and no qualifying substring is shorter than `5`.
**Example 2**
```text
Input: s = "AABXBAA", t = "AAB"
Output: "AAB"
```
The substring must contain two `A`s and one `B`. Both `"AAB"` (starting at index `0`) and `"BAA"` (starting at index `4`) qualify with length `3`; the one that starts earlier is returned.
**Example 3**
```text
Input: s = "abBA", t = "AAb"
Output: ""
```
`t` needs two uppercase `A`s, but `s` contains only one, and the lowercase `a` does not count as `A`.
Overview: Given a string and a pattern, return the shortest contiguous substring that contains every pattern character with its full multiplicity, choosing the leftmost one on ties and an empty string when none exists. It tests efficient string scanning, character counting with duplicates, careful edge cases and a clear complexity analysis.