76. Minimum Window Substring

76. Minimum Window Substring (Hard)

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.

Companies:
Facebook, Google, Amazon, LinkedIn, Microsoft, Apple, Uber, Bloomberg, Airbnb, Walmart Labs

Related Topics:
Hash Table, Two Pointers, String

Similar Questions:

• Substring with Concatenation of All Words (Hard)
• Minimum Size Subarray Sum (Medium)
• Sliding Window Maximum (Hard)
• Permutation in String (Medium)
• Smallest Range (Hard)
• Minimum Window Subsequence (Hard)

Solution 1. Two Pointers

// OJ: https://leetcode.com/problems/minimum-window-substring/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    string minWindow(string s, string t) {
        int cnt = 0, i = 0, j = 0, S = s.size(), T = t.size();
        int minLen = INT_MAX, begin = -1;
        unordered_map<char, int> m, seen;
        for (char c : t) m[c]++;
        while (j < S) {
            for (; j < S && cnt != T; ++j) {
                if (m.find(s[j]) == m.end()) continue;
                if (++seen[s[j]] <= m[s[j]]) ++cnt;
            }
            for (; cnt == T; ++i) {
                if (m.find(s[i]) == m.end()) continue;
                if (j - i < minLen) {
                    minLen = j - i;
                    begin = i;
                }
                if (--seen[s[i]] < m[s[i]]) --cnt;
            }
        }
        return begin == -1 ? "" : s.substr(begin, minLen);
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/minimum-window-substring/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems
class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> m(128, 0);
        for (char c : t) ++m[c];
        int begin = 0, end = 0, head = 0, cnt = t.size(), len = INT_MAX;
        while (end < s.size()) {
            if (m[s[end++]]-- > 0) --cnt;
            while (!cnt) {
                if (end - begin < len) len = end - (head = begin);
                if (m[s[begin++]]++ == 0) ++cnt;
            }
        }
        return len == INT_MAX ? "" : s.substr(head, len);
    }
};