Minimum Window Substring

Minimum Window Substring: 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 <= 10^5
s and t consist of uppercase and lowercase English letters.

Try this Problem on your own or check similar problems:

Solution:

Java
JavaScript
Python
C++

public String minWindow(String s, String t) {
    int[] freqMap = new int[128];
    int l1 = s.length(), l2 = t.length();
    int minLength = s.length() + 1, startIdx = - 1;

    if(l1 < l2) return "";
    for(char c: t.toCharArray()) freqMap[c]++;

    int start = 0, end = 0, cnt = 0;
    while(end < l1){
        if(freqMap[s.charAt(end)] > 0) cnt++;
        freqMap[s.charAt(end)]--;
        end++;

        while(cnt == l2){
            if(minLength > end - start){
                minLength = Math.min(minLength, end - start);
                startIdx = start;
            }
            if(freqMap[s.charAt(start)] == 0) cnt--;
            freqMap[s.charAt(start)]++;
            start++;
        }
    }

    return startIdx != -1 ? s.substring(startIdx, startIdx + minLength) : "";
}

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  const freqMap = new Array(128).fill(0);
  const l1 = s.length;
  const l2 = t.length;
  let minLength = l1 + 1;
  let startIdx = -1;

  if (l1 < l2) {
    return "";
  }

  for (const c of t) {
    freqMap[c.charCodeAt()]++;
  }

  let start = 0;
  let end = 0;
  let cnt = 0;

  while (end < l1) {
    if (freqMap[s.charCodeAt(end)] > 0) {
      cnt++;
    }
    freqMap[s.charCodeAt(end)]--;
    end++;

    while (cnt === l2) {
      if (minLength > end - start) {
        minLength = Math.min(minLength, end - start);
        startIdx = start;
      }
      freqMap[s.charCodeAt(start)]++;
      if (freqMap[s.charCodeAt(start)] > 0) {
        cnt--;
      }
      start++;
    }
  }

  return startIdx !== -1 ? s.substring(startIdx, startIdx + minLength) : "";
};

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        freqMap = [0] * 128
        l1 = len(s)
        l2 = len(t)
        minLength = l1 + 1
        startIdx = -1

        if l1 < l2:
            return ""

        for c in t:
            freqMap[ord(c)] += 1

        start = 0
        end = 0
        cnt = 0

        while end < l1:
            if freqMap[ord(s[end])] > 0:
                cnt -= 1
            freqMap[ord(s[end])] -= 1
            end += 1

            while cnt == l2:
                if minLength > end - start:
                    minLength = min(minLength, end - start)
                    startIdx = start
                freqMap[ord(s[start])] += 1
                if freqMap[ord(s[start])] > 0:
                    cnt += 1
                start += 1

        return s[startIdx: startIdx + minLength] if startIdx != -1 else ""

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> freqMap(128, 0);
        int l1 = s.length();
        int l2 = t.length();
        int minLength = l1 + 1;
        int startIdx = -1;

        if (l1 < l2) {
            return "";
        }

        for (char c : t) {
            freqMap[c]++;
        }

        int start = 0;
        int end = 0;
        int cnt = 0;

        while (end < l1) {
            if (freqMap[s[end]] > 0) {
                cnt++;
            }
            freqMap[s[end]]--;
            end++;

            while (cnt == l2) {
                if (minLength > end - start) {
                    minLength = min(minLength, end - start);
                    startIdx = start;
                }
                freqMap[s[start]]++;
                if (freqMap[s[start]] > 0) {
                    cnt--;
                }
                start++;
            }
        }

        return (startIdx != -1) ? s.substr(startIdx, minLength) : "";

    }
};

Time/Space Complexity:

Time Complexity: O(l1) where l1 is the length of longer (first) string
Space Complexity: O(1)

Explanation:

Since we're looking for smallest size window we utilize the implementation from Minimum Size Subarray Sum where we push the end pointer towards the end of input (array or string) but each time when we get a valid window we try to shorten it. We use freqMap to record letter occurrences of t, and we keep cnt which increases or decrease if we find the letter from t in s and include it in the window or drop it out of window hoping we will have a smaller window. We keep the minLength to record the shortest window/substring and startIdx to know where the window/substring starts. There are two operations that are expanding and shrinking the window with window validity being expressed as cnt == l2 (all letters from t found in string s):

Expand the window if(freqMap[s.charAt(end)] > 0) cnt++;, we check if the current character has been found in string t (its freqMap will be >0), and if it has been we increment the cnt since we found a new letter from t in string s. We also expand the window by moving end to the right end++, and then we decrement letter frequency freqMap[s.charAt(end)]-- (note that all other letters from the map that are not occuring in the string t will have map value 0, so decrementing them will produce a negative number which is ok since they're we're not interested in them)
Shrink the window (when a valid window is found) if(freqMap[s.charAt(start)] == 0) cnt--; We only decrement the cnt if current freqMap value is 0 since that means that letter is present in string t (all other letters will have negative value) and we're dropping it from the window. We move the start to the right side start++ and we increment the freqMap for the current letter freqMap[s.charAt(start)]++;. Again note that letters that aren't occurring in the string t will never change the cnt, since their initial freqMap value will be 0 and we will have the same number of increment (passing them with start pointer, when shrinking the window) and decrements (passing them with end pointer, when expanding the window) so that invariant will hold (their value will always be negative or 0).

Since we are iterating over the whole string s the time complexity is O(l1), we also have constant space complexity since we're only storing uppercase and lowercase English letters in the freqMap.

Example 1:​

Example 2:​

Example 3:​

Constraints:​

Solution:​

Time/Space Complexity:​

Explanation:​