Minimum Window Substring

Problem Description

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.

Intuition

We need to find the shortest substring of s that contains all characters from t.

Store the character frequencies of t in a hash map, then use a sliding window to find the minimum substring.

Track how many unique characters have been fully satisfied in the current window.

Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {

public:

    string minWindow(string s, string t) {
    
        unordered_map<char, int> mp;
        int n = s.size();
        int m = t.size();

        for(int i = 0; i < m; i++){
            mp[t[i]]++;
        }

        int minStart = 0, minLen = INT_MAX;

        int left = 0;

        int counter = mp.size(); /// determine all the character is used.
  
        for(int right = 0; right < n; right++) {

            char ch = s[right];

            if(mp.count(ch)) {
                mp[ch]--;
                if(mp[ch] == 0) {
                    counter--;
                }
            }
            
            while(counter == 0){
                if(right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }

                char ch = s[left];

                if(mp.count(ch)) {
                    mp[ch]++;
                    if(mp[ch] > 0) {
                        counter++;
                    }
                }
                left++;
            }
        }

        if (minLen == INT_MAX){
            return "";
        }
        return s.substr(minStart, minLen);
    }

};