Skip to content

minimum-window-substring.md

Latest commit

 

History

History
267 lines (189 loc) · 7.62 KB

minimum-window-substring.md

File metadata and controls

267 lines (189 loc) · 7.62 KB

76. Minimum Window Substring - 最小覆盖子串

Tags - 题目标签

Description - 题目描述

EN:

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

 

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

 

Constraints:

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s and t consist of uppercase and lowercase English letters.

 

Follow up: Could you find an algorithm that runs in O(m + n) time?

ZH-CN:

给你一个字符串 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) 时间内解决此问题的算法吗？

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language Runtime Memory Submission Time
typescript 1056 ms 50.1 MB 2022/05/30 17:50 
function minWindow(s: string, t: string): string {
  if (s.length < t.length) {
    return '';
  }

  const tMap: Record<string, number> = {};

  let min = +Infinity;

  let res = '';

  let window = '';

  const windowMap: Record<string, number> = {};

  for (let i = 0; i < t.length; i++) {
    tMap[t[i]] = tMap[t[i]] ? tMap[t[i]] + 1 : 1;
  }

  function isValid(): boolean {
    let flag = true;
    const iter = Object.entries(tMap);

    for (let i = 0; i < iter.length; i++) {
      const [k, v] = iter[i];

      if (windowMap[k] === undefined) {
        flag = false;
        break;
      }
      
      if (v > windowMap[k]) {
        flag = false;
        break;
      }
    }

    return flag;
  }

  let start = 0, end = 1;

  window = s.slice(start, end);

  windowMap[window[0]] = 1;

  while (start <= end && end <= s.length) {
    if (isValid()) {
      if (window.length < min) {
        res = window;
        min = window.length;
      }
      const cnt = windowMap[window[0]];
      windowMap[window[0]] = cnt - 1;
      start++;
      window = s.slice(start, end);
    } else {
      end++;
      window = s.slice(start, end);
      const last = window[window.length - 1];
      windowMap[last] = windowMap[last] ? windowMap[last] + 1 : 1;
    }
  }

  return res;
};

My Notes - 我的笔记

参考官方题解的滑动窗口法写的解法：

function minWindow(s: string, t: string): string {
  if (s.length < t.length) {
    return '';
  }

  const tMap: Record<string, number> = {};

  let min = +Infinity;

  let res = '';

  let window = '';

  const sMap: Record<string, number> = {};

  for (let i = 0; i < t.length; i++) {
    tMap[t[i]] = tMap[t[i]] ? tMap[t[i]] + 1 : 1;
  }

  function isValid(): boolean {
    let flag = true;
    const iter = Object.entries(tMap);

    for (let i = 0; i < iter.length; i++) {
      const [k, v] = iter[i];

      if (sMap[k] === undefined) {
        flag = false;
        break;
      }
      
      if (v > sMap[k]) {
        flag = false;
        break;
      }
    }

    return flag;
  }

  let start = 0, end = 1;

  window = s.slice(start, end);

  sMap[window[0]] = 1;

  while (start <= end && end <= s.length) {
    if (isValid()) {
      if (window.length < min) {
        res = window;
        min = window.length;
      }
      const cnt = sMap[window[0]];
      sMap[window[0]] = cnt - 1;
      start++;
      window = s.slice(start, end);
    } else {
      end++;
      window = s.slice(start, end);
      const last = window[window.length - 1];
      sMap[last] = sMap[last] ? sMap[last] + 1 : 1;
    }
  }

  return res;
};

讲道理时间复杂度是一样的，我也不知道为什么执行用时那么长...

时间复杂度：最坏情况下左右指针对 $s$ 的每个元素各遍历一遍，哈希表中对 $s$ 中的每个元素各插入、删除一次，对 $t$ 中的元素各插入一次。每次检查是否可行会遍历整个 $t$ 的哈希表，哈希表的大小与字符集的大小有关，设字符集大小为 $C$，则渐进时间复杂度为 $O(C⋅∣s∣+∣t∣)$。 空间复杂度：这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，我们设字符集大小为 $C$ ，则渐进空间复杂度为 $O(C)$。