算法leetcode｜76. 最小覆盖子串（rust重拳出击）

---

---

76. 最小覆盖子串：

给你一个字符串 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 <= 10⁵
• s 和 t 由英文字母组成

---

进阶：

你能设计一个在 o(m + n) 时间内解决此问题的算法吗？

---

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 直接采用双层循环暴力解决的话，时间复杂度会比较高，恐怕过不了用例，没有去试。
• 题目并不要求字符的顺序，只要求了每种字符的数量，那首先就想到要做计数。
• 接下来考虑如何降低时间复杂度，每次循环都从新匹配子串是低效的，要尽可能复用，滑动窗口在这里非常合适，使用双指针，先直接移动右指针找到第一个满足条件的子串，记下长度作为备选结果，接下来移动左指针，当不满足覆盖子串的条件时就继续移动右置针直到满足覆盖子串d饿条件，并比较子串的长度，取较小的子串长度作为备选结果，重复该操作，直到循环遍历完毕。
• 如何高效判断遍历的子串已经满足覆盖子串呢？字符计数这时候就要大展拳脚了，先在遍历字符串 s 之前，先对字符串 t 进行一次遍历，做初始化计数，记录下每种字符的个数（题解中这里使用了减法，使用加法也是可以的，只是后面的加减法就要变），在遍历 s 时，移动右指针就是延长了覆盖子串，同时修改计数，这里的加减法计算要和前面初始化的相反，判断计数是否为0，如果变为0则表示，这种字符的个数已经没有差异了，但是我们需要覆盖了 t 中的每一种字符，所以需要判断 26 个字符的个数是不是都够了，如果都够了，就是满足了覆盖子串，接下来就移动左指针，同时修改计数，这里的加减计算要和右指针移动的相反。
• 当某个字符的计数变为0时，我们需要判断 26 种字符的字符个数是不是都满足了，这里就需要26次循环，是否有更高效的办法呢？我们可以额外增加一个变量记录有差异的字符种类数（记录有差异的字符数也是可以的，但是后面的逻辑会有一点区别，思想大致相同）， 初始化时顺便初始化该变量，在遍历匹配中，每当有字符计数变为0，就修改这个变量，如果这个变量变为0则表示完全覆盖，从而提高效率。
• 只看文字可能不便理解，建议对照着熟悉的语言的题解一起看，希望可以有助学习理解。

题解：

rust：

impl Solution {pub fn min_window(s: String, t: String) -> String {// 少于目标字符串中数量的字符数量let mut diff_char_count = 0;// 字符计数器let mut cnt = vec![0; 128];// 初始化t.as_bytes().iter().for_each(|&b| {// 计数减少cnt[b as usize] -= 1;if cnt[b as usize] == -1 {// 差异字符数增加diff_char_count += 1;}});// 覆盖子串结果信息let (mut ans_len, mut ans_l) = (usize::MAX, usize::MAX);// 开始滑动窗口let s_len = s.len();let (mut l, mut r) = (0, 0);while r < s_len {// 计数增加cnt[s.as_bytes()[r] as usize] += 1;// 向右移动右边界后，可能该字符数量没有差异了if cnt[s.as_bytes()[r] as usize] == 0 {// 差异字符数减少diff_char_count -= 1;// 差异字符数减少后可能为0了if diff_char_count == 0 {// 向右滑动左边界，直到会有差异，取满足要求的最小串while cnt[s.as_bytes()[l] as usize] > 0 {cnt[s.as_bytes()[l] as usize] -= 1;l += 1;}// 更新结果if r - l + 1 < ans_len {ans_len = r - l + 1;ans_l = l;}// 向右移动左边界，差异字符数增加cnt[s.as_bytes()[l] as usize] -= 1;l += 1;diff_char_count += 1;}}r += 1;}return if ans_l == usize::MAX {"".to_string()} else {s[ans_l..ans_l + ans_len].to_string()}}
}

---

go：

func minWindow(s string, t string) string {// 少于目标字符串中数量的字符数量diffCharCount := 0// 字符计数器cnt := make([]int, 128)// 初始化for _, c := range t {// 计数减少cnt[c]--if cnt[c] == -1 {// 差异字符数增加diffCharCount++}}// 覆盖子串结果信息ansLen, ansL := math.MaxInt32, -1// 开始滑动窗口sLen := len(s)l, r := 0, 0for r < sLen {// 计数增加cnt[s[r]]++// 向右移动右边界后，可能该字符数量没有差异了if cnt[s[r]] == 0 {// 差异字符数减少diffCharCount--// 差异字符数减少后可能为0了if diffCharCount == 0 {// 向右滑动左边界，直到会有差异，取满足要求的最小串for cnt[s[l]] > 0 {cnt[s[l]]--l++}// 更新结果if r-l+1 < ansLen {ansLen = r - l + 1ansL = l}// 向右移动左边界，差异字符数增加cnt[s[l]]--l++diffCharCount++}}r++}if ansL == -1 {return ""} else {return s[ansL : ansL+ansLen]}
}

---

c++：

class Solution {
public:string minWindow(string s, string t) {// 少于目标字符串中数量的字符数量int diffCharCount = 0;// 字符计数器int cnt[128];memset(cnt, 0, sizeof(cnt));// 初始化const int tLen = t.length();for (int i = 0; i < tLen; ++i) {if (--cnt[t[i]] == -1) {// 差异字符数增加++diffCharCount;}}// 覆盖子串结果信息int ansLen = INT_MAX, ansL = -1;// 开始滑动窗口const int sLen = s.length();int l = 0, r = -1;while (++r < sLen) {// 向右移动右边界后，可能该字符数量没有差异了if (++cnt[s[r]] == 0) {// 差异字符数减少后可能为0了if (--diffCharCount == 0) {// 向右滑动左边界，直到会有差异，取满足要求的最小串while (--cnt[s[l++]] >= 0) {// nothing}// 差异字符数增加++diffCharCount;// 更新结果if (r - l + 2 < ansLen) {ansLen = r - l + 2;ansL = l - 1;}}}}return ansL == -1 ? "" : s.substr(ansL, ansLen);}
};

---

python：

class Solution:def minWindow(self, s: str, t: str) -> str:# 少于目标字符串中数量的字符数量diff_char_count = 0# 字符计数器cnt = collections.defaultdict(int)# 初始化for c in t:# 计数减少cnt[c] -= 1if cnt[c] == -1:# 差异字符数增加diff_char_count += 1# 覆盖子串结果信息ans_len, ans_l = float("inf"), -1# 开始滑动窗口s_len = len(s)l, r = 0, 0while r < s_len:# 计数增加cnt[s[r]] += 1# 向右移动右边界后，可能该字符数量没有差异了if cnt[s[r]] == 0:# 差异字符数减少diff_char_count -= 1# 差异字符数减少后可能为0了if diff_char_count == 0:# 向右滑动左边界，直到会有差异，取满足要求的最小串while cnt[s[l]] > 0:cnt[s[l]] -= 1l += 1# 更新结果if r - l + 1 < ans_len:ans_len = r - l + 1ans_l = l# 向右移动左边界，差异字符数增加cnt[s[l]] -= 1l += 1diff_char_count += 1r += 1return "" if ans_l == -1 else s[ans_l: ans_l + ans_len]

---

java：

class Solution {public String minWindow(String s, String t) {// 少于目标字符串中数量的字符数量int diffCharCount = 0;// 字符计数器final int[] cnt = new int[128];// 初始化final int tLen = t.length();for (int i = 0; i < tLen; ++i) {if (--cnt[t.charAt(i)] == -1) {// 差异字符数增加++diffCharCount;}}// 覆盖子串结果信息int ansLen = Integer.MAX_VALUE, ansL = -1;// 开始滑动窗口final int sLen = s.length();int       l    = 0, r = -1;while (++r < sLen) {// 向右移动右边界后，可能该字符数量没有差异了if (++cnt[s.charAt(r)] == 0) {// 差异字符数减少后可能为0了if (--diffCharCount == 0) {// 向右滑动左边界，直到会有差异，取满足要求的最小串while (--cnt[s.charAt(l++)] >= 0) {// nothing}// 差异字符数增加++diffCharCount;// 更新结果if (r - l + 2 < ansLen) {ansLen = r - l + 2;ansL = l - 1;}}}}return ansL == -1 ? "" : s.substring(ansL, ansL + ansLen);}
}

---

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

---