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 (Java)

class Solution {
    public String minWindow(String s, String t) {
        int[] map = new int[128];
        for (int i = 0; i < t.length(); i++) {
            map[t.charAt(i) - 'A']++;
        }
        int count = t.length();
        int begin = 0;
        int end = 0;
        int d = Integer.MAX_VALUE;
        int head = 0;
        while (end < s.length()) {
            if (map[s.charAt(end++) - 'A']-- > 0) {
                count--;
            }
            while (count == 0) {
                if (end - begin < d) {
                    d = end - begin;
                    head = begin;
                }
                if (map[s.charAt(begin++) - 'A']++ == 0) {
                    count++;
                }
            }
        }
        return d == Integer.MAX_VALUE ? "" : s.substring(head, head + d);
    }
}

Solution (Javascript)

/**
 * @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).