Skip to content

Minimum Window Substring⚓︎

Link

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 test cases will be generated such that the answer is unique.

A substring is a contiguous non-empty sequence of characters within a string.

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.

Solution⚓︎

 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
class Solution {
public:
    string minWindow(string s, string t) {
        if (s.length() < t.length()) return "";

        vector<int> cnts(255, 0);
        for (char ch : t) cnts[ch]--;

        int len = INT_MAX;
        int start = 0;
        int debt = t.length();
        for (int left = 0, right = 0; right < s.length(); right++) {
            if (cnts[s[right]]++ < 0) {
                debt--;
            }

            if (debt == 0) {
                while (cnts[s[left]] > 0) {
                    cnts[s[left]]--;
                    left++;
                }
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    start = left;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

Another way of writing (with hash map):

 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
class Solution {
public:
    string minWindow(string s, string t) {
        if (s.length() < t.length()) return "";

        unordered_map<char, int> cnts;
        for (char ch : t) cnts[ch]--;

        int len = INT_MAX;
        int start = 0;
        int debt = t.length();
        for (int left = 0, right = 0; right < s.length(); right++) {
            if (cnts.find(s[right]) != cnts.end() && cnts[s[right]]++ < 0) {
                debt--;
            }

            if (debt == 0) {
                while (cnts.find(s[left]) == cnts.end() || cnts[s[left]] > 0) {
                    if (cnts.find(s[left]) != cnts.end()) {
                        cnts[s[left]]--;
                    }
                    left++;
                }
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    start = left;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

Easier way of writing:

 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
class Solution {
public:
    string minWindow(string s, string t) {
        if (s.length() < t.length()) return "";

        unordered_map<char, int> hashS, hashT;
        for (char ch : t) hashT[ch]++;

        int count = 0, len = INT_MAX, start = 0;
        for (int left = 0, right = 0; right < s.length(); right++) {
            hashS[s[right]]++;
            if (hashS[s[right]] <= hashT[s[right]]) count++;

            while (left <= right && hashS[s[left]] > hashT[s[left]]) {
                hashS[s[left]]--;
                left++;
            }
            if (count == t.length()) {
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    start = left;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};