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 "".

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

How to Solve

The question asks us to return the minimum window from the string S which has all the characters of the string T. Let us call a window desirable if it has all the characters from T.

We can use a simple sliding window approach to solve this problem. In any sliding window based problem we have two pointers. One right pointer whose job is to expand the current window, and then we have the left pointer whose job is to contract a given window. At any point in time only one of these pointers move and the other one remains fixed.

The solution is pretty intuitive. We keep expanding the window by moving the right pointer. When the window has all the desired characters, we contract (if possible) and save the smallest window till now.

The answer is the smallest desirable window.

Test Cases

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.

Solution

char* minWindow(char* s, char* t) {
    int i    = 0;
    int j    = 0;
    int tlen = strlen(t);
    int slen = strlen(s);
    int counts[256] = { 0 };
    int win[2] = { 0, INT_MAX };

    for (int i = 0; i < tlen; i++) {
        counts[t[i]]++;
    }
    while (j < slen) {
        if (counts[s[j]] > 0) {
            tlen--;
        }
        counts[s[j]]--;
        j++;
        while (tlen == 0) {
            if (j - i < win[1] - win[0]) {
                win[0] = i; win[1] = j;
            }
            counts[s[i]]++;
            if (counts[s[i]] > 0) {
                tlen++;
            }
            i++;
        }
    }
    return (win[1] != INT_MAX) 
           ? strndup(&s[win[0]], win[1] - win[0]) 
           : "";
}
class Solution {
public:
    string minWindow(string s, string t) {
        int tmap[256] = {0}, smap[256] = {0};
        int requiredChars = 0, foundChars = 0;
        int left = 0, right = 0, minlength = -1, start = 0, end=0;
        char c;
        for(int i=0; i<t.length(); i++) {
            char c = t[i];
            if (tmap[c] == 0) requiredChars++;
            tmap[c]++;
        }
        while(right < s.length()) {
            c = s[right];
            smap[c]++;
            if (tmap[c] > 0 && tmap[c] == smap[c]) {
                foundChars++;
            }
            while(left <= right && foundChars == requiredChars) {
                c = s[left];
                if (minlength == -1 || minlength > right - left + 1) {
                    minlength = right - left + 1;
                    start = left;
                    end = right;
                }
                smap[c]--;
                if (tmap[c] > 0 && tmap[c] > smap[c]) {
                    foundChars--;
                }
                left++;
            }

            right++;
        }
        return minlength == -1 ? "" : s.substr(start, minlength);
    }
};
class Solution {
    public String minWindow(String s, String t) {
        int[] smap = new int[256];
        int[] tmap = new int[256];
        int requiredChars = 0;
        char c;
        for(int i=0; i<t.length(); i++) {
            c = t.charAt(i);
            if (tmap[c] == 0) requiredChars++;
            tmap[c]++;
        }
        int left = 0, right = 0;
        int foundChars = 0;
        int start = 0, end = 0, minlength = -1;
        while(right < s.length()) {
            c = s.charAt(right);
            smap[c]++;
            if (tmap[c] > 0 && tmap[c] == smap[c]) {
                foundChars++;
            }
            while(left <= right && foundChars == requiredChars) {
                c = s.charAt(left);
                if (minlength == -1 || minlength > right - left + 1) {
                    minlength = right - left + 1;
                    start = left;
                    end = right;
                }
                smap[c]--;
                if (tmap[c] > 0 && tmap[c] > smap[c]) {
                    foundChars--;
                }
                left++;
            }

            right++;
        }

        return minlength == -1 ? "" : s.substring(start, end+1);
    }
}
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        tmap, smap = [0]*256, [0]*256
        requiredChars, foundChars = 0, 0
        left, right, minlength, start, end = 0, 0, -1, 0, 0
        for c in t:
            if tmap[ord(c)] == 0:
                requiredChars += 1
            tmap[ord(c)]+=1
        while right < len(s):
            c = ord(s[right])
            smap[c]+=1
            if tmap[c] > 0 and tmap[c] == smap[c]:
                foundChars += 1
            while left <= right and foundChars == requiredChars:
                c = ord(s[left])
                if minlength == -1 or minlength > right - left + 1:
                    minlength, start, end = right-left+1, left, right
                smap[c]-=1
                if tmap[c] > 0 and tmap[c] > smap[c]:
                    foundChars-=1
                left += 1
            right += 1
        return "" if minlength == -1 else s[start:end+1]
Time Complexity: O(n+m)
Space Complexity: O(n+m)