76. Minimum Window Substring

Problem

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Solution

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
  var map = {};
  var sLen = s.length;
  var tLen = t.length;
  var count = tLen;
  var min = Number.MAX_SAFE_INTEGER;
  var head = 0;
  var left = 0;
  var right = 0;

  if (!sLen || !tLen) return '';

  for (var i = 0; i < tLen; i++) {
    if (map[t[i]] === undefined) {
      map[t[i]] = 1
    } else {
      map[t[i]]++;
    }
  }

  while (right < sLen) {
    if (map[s[right]] !== undefined) {
      if (map[s[right]] > 0) count--;
      map[s[right]]--;
    }

    right++;

    while (count === 0) {
      if (right - left < min) {
        min = right - left;
        head = left;
      }

      if (map[s[left]] !== undefined) {
        if (map[s[left]] === 0) count++;
        map[s[left]]++;
      }

      left++;
    }
  }

  return min === Number.MAX_SAFE_INTEGER ? '' : s.substr(head, min);
};

Explain:

see Here is a 10-line template that can solve most 'substring' problems.

用哈希表保存各字符的数量，双指针表示当前窗口，用计数器来判断是否符合条件。符合条件后，记录窗口位置、最小值；更新双指针、计数器。

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).