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.
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.
Implement `shortest_covering_substring(s, t)`, which returns that substring as a string.
**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.
- No length or index can exceed 2^31 - 1, so 32-bit integers suffice in every language.
**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.
Constraints
- 1 <= len(s) <= 10^5
- 1 <= len(t) <= 10^5
- s and t consist of uppercase and lowercase English letters.
Examples
Input: ('AXXBXCXXAB', 'ABC')
Expected Output: 'CXXAB'
Explanation: Source Example 1: the only length-5 window holding A, B and C is indices 5-9, which ends at the last index; the other covering windows have length 6 or more.
Input: ('AABXBAA', 'AAB')
Expected Output: 'AAB'
Explanation: Source Example 2: 'AAB' (index 0) and 'BAA' (index 4) tie at length 3; the smaller start index wins.
Hints
- A substring qualifies exactly when, for every character, it contains at least as many copies as t does. Repeated characters in t must be counted, not just checked for presence.
- If a substring qualifies, every longer substring that contains it also qualifies; and if t is longer than s, nothing can qualify.
- 'a' and 'A' are different characters, and when two qualifying substrings have the same length, the one that starts at the smaller index wins.