Smallest Substring Containing

• Time : O(n + m)
• Space : O(m)

using namespace std;

string smallestSubstringContaining(string bigString, string smallString) {
    unordered_map<char, int> smp, bmp;
    for(auto& ch : smallString)
        smp[ch]++;
    int len = INT_MAX, n = bigString.length(), count = smp.size(), pos = -1, l = 0, r = 0;

	while(r < n) {
        while(r < n and count > 0) {
            char ch = bigString[r++];
            if(smp.count(ch) and smp[ch] == ++bmp[ch]) count--;
        }
        while(l < r and count == 0) {
            if(len > r - l) {
                pos = l; len = r - l;
            }
            char ch = bigString[l++];
            if(smp.count(ch) and smp[ch] == bmp[ch]--) count++;
        }
    }
    return pos == -1 ? "" : bigString.substr(pos, len);
}