最小覆盖子串

Tips

题目类型: 滑动窗口

题目

给你一个字符串 s 和 t, 请返回 s 中涵盖 t 所有字符的最小子串. 如果 s 中不存在涵盖 t 所有字符的子串, 则返回空字符串.

注意: 如果 s 中存在这样的子串, 我们保证它是唯一的答案.

提示:

m == s.length
n == t.length
1 <= m, n <= 10⁵
s 和 t 由英文字母组成

示例

输入: s = "ADOBECODEBANC", t = "ABC"

输出: BANC

题解

这是个很经典的滑动窗口问题, 该题跟 438. 找到字符串中所有字母异位词解法一致.

首先创建一个名叫 needMap 的哈希表, 用于映射 t 的每个元素
定义一个 count 的变量, 初始化为 0, 当 windowMap[s[right]] === needMap[s[right]] 时, 让 count++
因此当 count === needMap.size 时, 就保证了 windowMap 中已经覆盖了 t 字符串
接着就可以缩小窗口了, 缩小窗口的代码跟扩大窗口的代码相反, 即直到窗口中的字符串不再符合要求, left 不再继续移动
重复这个过程, 直到 right 到了最右边退出循环

JavaScript
Rust

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  let minStr = ''

  const needMap = new Map()
  for (const ch of t) {
    needMap.set(ch, needMap.has(ch) ? needMap.get(ch) + 1 : 1)
  }
  
  const windowMap = new Map()
  let start = 0
  let end = 0
  let count = 0

  while (end < s.length) {
    const endCh = s[end++]

    if (needMap.has(endCh)) {
      windowMap.set(endCh, windowMap.has(endCh) ? windowMap.get(endCh) + 1 : 1)
      if (needMap.get(endCh) === windowMap.get(endCh)) count++
    }

    // 当 count ===  needMap.size, 说明找到了一个覆盖子串
    // 这个时候就可以收缩窗口了
    while (count === needMap.size) {
      const subStr = s.slice(start, end)
      if (minStr.length === 0 || subStr.length < minStr.length) minStr = subStr

      const startCh = s[start++]

      if (needMap.has(startCh)) {
        if (needMap.get(startCh) === windowMap.get(startCh)) count--
        windowMap.set(startCh, windowMap.get(startCh) - 1)
      }
    }
  }

  return minStr
}

use std::collections::HashMap;

pub fn min_window(s: String, t: String) -> String {
    let mut min_str = "";

    let mut need_map = HashMap::new();
    for letter in t.as_bytes() {
        *need_map.entry(*letter).or_insert(1) += 1;
    }

    let mut window_map = HashMap::new();
    let mut count = 0;
    let (mut start, mut end) = (0, 0);

    while end < s.len() {
        let end_letter = s.as_bytes()[end];
        end += 1;

        if need_map.contains_key(&end_letter) {
            *window_map.entry(end_letter).or_insert(1) += 1;

            if window_map.get(&end_letter) == need_map.get(&end_letter) {
                count += 1;
            }
        }

        while count == need_map.len() {
            let sub_str = &s[start..end];
            if min_str.len() == 0 || sub_str.len() < min_str.len() {
                min_str = sub_str;
            }

            let start_letter = s.as_bytes()[start];
            start += 1;

            if need_map.contains_key(&start_letter) {
                if window_map.get(&start_letter) == need_map.get(&start_letter) {
                    count -= 1;
                }

                window_map.entry(start_letter).and_modify(|e| *e -= 1);
            }
        }
    }

    min_str.to_string()
}

题目​

题解​

题目

题解