题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2：
输入：s = “a”, t = “a”
输出：“a”
解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成
进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
java代码
这个问题可以使用滑动窗口算法来解决。滑动窗口算法通常用于找到包含一组特定字符或元素的最短子串。
以下是使用Java实现的滑动窗口算法来找到涵盖字符串 t 所有字符的最小子串：
class Solution {
public String minWindow(String s, String t) {
int[] tChars = new int[128]; // 用于存储字符串 t 中各字符的出现次数
for (char c : t.toCharArray()) {
tChars[c]++;
}
int left = 0, right = 0; // 滑动窗口的左右指针
int minLen = Integer.MAX_VALUE; // 最小子串的长度
int minStart = 0; // 最小子串的起始位置
int remaining = t.length(); // t 中未被覆盖的字符数
while (right < s.length()) {
if (tChars[s.charAt(right)] > 0) {
remaining--;
}
tChars[s.charAt(right)]--;
while (remaining == 0) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
tChars[s.charAt(left)]++;
if (tChars[s.charAt(left)] > 0) {
remaining++;
}
left++;
}
right++;
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}
}
使用滑动窗口来找到最小子串
首先，构建一个 tChars 数组来记录字符串 t 中各字符的出现次数。然后，使用左右指针 left 和 right 来维护滑动窗口，同时也维护变量 remaining 来表示 t 中未被覆盖的字符数。在循环中，不断向右移动 right 指针，直到覆盖了所有 t 中的字符，然后向右移动 left 指针来尽量缩小子串的长度。最终，返回找到的最小子串。
这个算法的时间复杂度是 O(S + T)，其中 S 是字符串 s 的长度，T 是字符串 t 的长度。
python 代码
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
target_counts = Counter(t)
required_chars = len(target_counts)
left, right = 0, 0
min_length = float('inf')
min_window = ""
while right < len(s):
if s[right] in target_counts:
target_counts[s[right]] -= 1
if target_counts[s[right]] == 0:
required_chars -= 1
while required_chars == 0:
if right - left + 1 < min_length:
min_length = right - left + 1
min_window = s[left:right+1]
if s[left] in target_counts:
target_counts[s[left]] += 1
if target_counts[s[left]] > 0:
required_chars += 1
left += 1
right += 1
return min_window
C++代码文章来源：https://www.toymoban.com/news/detail-738952.html
#include <string>
#include <unordered_map>
#include <climits>
class Solution {
public:
std::string minWindow(std::string s, std::string t) {
std::unordered_map<char, int> target_counts;
int required_chars = t.length();
int left = 0, right = 0;
int min_length = INT_MAX;
int min_start = 0;
for (char c : t) {
target_counts[c]++;
}
while (right < s.length()) {
if (target_counts.find(s[right]) != target_counts.end()) {
target_counts[s[right]]--;
if (target_counts[s[right]] >= 0) {
required_chars--;
}
}
while (required_chars == 0) {
if (right - left + 1 < min_length) {
min_length = right - left + 1;
min_start = left;
}
if (target_counts.find(s[left]) != target_counts.end()) {
target_counts[s[left]]++;
if (target_counts[s[left]] > 0) {
required_chars++;
}
}
left++;
}
right++;
}
if (min_length == INT_MAX) {
return "";
}
return s.substr(min_start, min_length);
}
};
这段代码使用了C++的std::unordered_map来统计字符串t中每个字符的频率。然后，通过滑动窗口算法，在字符串s上移动左右指针，维护一个窗口，确保窗口内包含了字符串t中的所有字符。当窗口包含了所有t中的字符时，通过比较窗口长度来更新最小子串的起始和结束位置。最后，返回最小子串。文章来源地址https://www.toymoban.com/news/detail-738952.html
到了这里，关于LeetCode----76. 最小覆盖子串的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
