76. Minimum Window Substring

• Difficulty: Hard

• Topics: Hash Table, Two Pointers, String, Sliding Window

• Similar Questions:

  • Substring with Concatenation of All Words

  • Minimum Size Subarray Sum

  • Sliding Window Maximum

  • Permutation in String

  • Smallest Range Covering Elements from K Lists

  • Minimum Window Subsequence

Problem:

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.

Solutions:

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> charCount;
        for (auto c : t) {
            ++charCount[c];
        }

        int r = 0;
        int l = 0;
        int count = t.length();
        string ret;
        int len = INT_MAX;


        for (r = 0; r < s.length(); ++r) {
            char c = s[r];
            if (charCount.count(c) == 0) continue;
            --charCount[c];
            if (charCount[c] >= 0)  --count;
            if (charCount[c] == 0 && count == 0) {  
                while (true) {
                    if (charCount.count(s[l]) == 0) {
                        ++l;
                    } else {
                        char lastC = s[l];
                        ++l;
                        ++charCount[lastC];
                        if (charCount[lastC] == 1) {
                            ++count;
                            break;
                        }
                    }
                }

                if (r - l + 2 < len) {
                    len = r - l + 2;
                    ret = s.substr(l-1, len);
                }
            }
        }

        return len == INT_MAX ? "" : ret;
    }
};