当前位置： 面试刷题>> 最小覆盖子串(经典算法150题)
### 题目描述
**题目：最小覆盖子串**
给定一个字符串 `s` 和一个字符串 `t`，找出 `s` 中包含 `t` 的所有字符的最小子串。如果 `s` 中不存在这样的子串，则返回空字符串。需要注意的是，`t` 中的字符不需要在 `s` 中以连续的顺序出现，但必须在 `s` 的子串中每个字符至少出现一次，且子串的长度要尽可能小。
**示例 1**:
```
输入: s = "ADOBECODEBANC", t = "ABC"
输出: "BANC"
```
**示例 2**:
```
输入: s = "abb", t = "abb"
输出: "abb"
```
**示例 3**:
```
输入: s = "ab", t = "ab"
输出: "ab"
```
**示例 4**:
```
输入: s = "axxxxyyyyb", t = "xyy"
输出: "xyyyb"
```
### 解题思路
为了找到包含 `t` 中所有字符的最小子串，我们可以使用滑动窗口和哈希表的方法。具体步骤如下：
1. **初始化**：使用两个哈希表 `need` 和 `window`，其中 `need` 记录字符串 `t` 中每个字符需要的数量，`window` 记录当前窗口中每个字符的数量。同时，初始化窗口的左右指针 `left` 和 `right` 都指向字符串 `s` 的起始位置，以及两个变量 `matched` 来记录当前窗口中满足 `t` 条件的字符个数，和 `result` 来记录最小覆盖子串的起始位置和长度。
2. **移动右指针**：不断移动右指针 `right`，扩大窗口，并更新 `window` 和 `matched`。如果 `window` 中某个字符的数量满足了 `need` 的要求，则 `matched` 加一。
3. **尝试移动左指针**：当 `matched` 等于 `t` 的长度时，表示当前窗口已经包含了 `t` 的所有字符。此时尝试移动左指针 `left` 来缩小窗口，并更新 `result`（如果当前窗口大小小于 `result` 记录的大小）。在移动左指针的过程中，如果移除了 `t` 中需要的字符，则 `matched` 减一。
4. **重复步骤 2 和 3**，直到右指针到达字符串 `s` 的末尾。
5. **返回结果**：如果找到了满足条件的最小覆盖子串，则返回该子串；否则，返回空字符串。
### PHP 代码示例
```php
function minWindow($s, $t) {
$need = array_count_values(str_split($t));
$window = [];
$left = $right = 0;
$matched = 0;
$result = ['start' => 0, 'len' => PHP_INT_MAX];
while ($right < strlen($s)) {
$c = $s[$right];
if (isset($need[$c])) {
$window[$c] = isset($window[$c]) ? $window[$c] + 1 : 1;
if ($window[$c] == $need[$c]) {
$matched++;
}
}
$right++;
// 尝试缩小窗口
while ($matched == count($need)) {
if ($right - $left < $result['len']) {
$result = ['start' => $left, 'len' => $right - $left];
}
$d = $s[$left];
$left++;
if (isset($need[$d])) {
if ($window[$d] == $need[$d]) {
$matched--;
}
$window[$d]--;
}
}
}
return $result['len'] == PHP_INT_MAX ? "" : substr($s, $result['start'], $result['len']);
}
```
### Python 代码示例
```python
def minWindow(s: str, t: str) -> str:
need = collections.Counter(t)
window = collections.defaultdict(int)
left, right = 0, 0
matched = 0
result = float('inf'), None, None
while right < len(s):
c = s[right]
if c in need:
window[c] += 1
if window[c] == need[c]:
matched += 1
right += 1
while matched == len(need):
if right - left < result[0]:
result = (right - left, left, right)
d = s[left]
left += 1
if d in need:
if window[d] == need[d]:
matched -= 1
window[d] -= 1
return "" if result[1] is None else s[result[1]:result[2]]
```
### JavaScript 代码示例
```javascript
function minWindow(s, t) {
const need = {};
for (const char of t) {
need[char] = (need[char] || 0) + 1;
}
let window = {};
let left = 0, right = 0;
let matched = 0;
let result = [0, Infinity]; // [start, length]
while (right < s.length) {
const c = s[right];
if (need[c]) {
window[c] = (window[c] || 0) + 1;
if (window[c] === need[c]) {
matched++;
}
}
right++;
while (matched === Object.keys(need).length) {
if (right - left < result[1]) {
result = [left, right - left];
}
const d = s[left];
left++;
if (need[d]) {
if (window[d] === need[d]) {
matched--;
}
window[d]--;
}
}
}
return result[1] === Infinity ? "" : s.substring(result[0], result[0] + result[1]);
}
```
希望这些示例能帮助你理解和解决“最小覆盖子串”的问题。