76. Minimum Window Substring

source: https://leetcode.com/problems/minimum-window-substring/

Question

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.

A substring is a contiguous sequence of characters within the string.

暴力法

用两个loop，一个是起始位置，一个是在剩余数组中去查询何时包含所有子字符串。

var minWindow = function (s, t) {
  let ret = "";
  for (let i1 = 0; i1 < s.length; i1++) {
    const arr = Array.from(t);
    for (let i2 = i1; i2 < s.length; i2++) {
      const index = arr.findIndex((v) => v === s[i2]);
      if (index > -1) {
        arr.splice(index, 1);
        if (arr.length === 0) {
          const v = s.slice(i1, i2 + 1);
          if (v.length < ret.length || !ret) ret = v;
          break;
        }
      }
    }
  }
  return ret;
};

时间复杂度是O(n2)。

滑动窗口

因为有两个loop，且是在数组中进行操作，很容易想到滑动窗口。

var minWindow = function (s, t) {
  const window = {};
  const need = {};
  for (let c of t) need[c] = (need[c] || 0) + 1;
  let left = 0;
  let right = 0;
  let valid = 0;
  let start = 0;
  let len = Number.MAX_SAFE_INTEGER;
  while (right < s.length) {
    const c = s[right];
    right++;
    if (need[c]) {
      window[c] = (window[c] || 0) + 1;
      if (window[c] === need[c]) valid++;
    }
    while (valid === Object.keys(need).length) {
      if (right - left < len) {
          start = left;
          len = right - left;
      }
      const d = s[left];
      left++;
      if (need[d]) {
        if (window[d] === need[d]) valid--;
        window[d]--;
      }
    }
  }
  return len === Number.MAX_SAFE_INTEGER ? '' : s.slice(start, start + len);
};

End

对于滑动窗口的模版要极为熟悉。