Time Cost

None

Code

#include <string>
#include <unordered_map>
#include <climits>
#include <algorithm>

class Solution {
public:
    std::string minWindow(std::string s, std::string t) {
        if (s.length() < t.length()) return "";

        std::unordered_map<char, int> map;
        // **Target** frequency map
        for (char ch : t) {
            map[ch]++;
        }

        int start = -1;
        int count = 0;
        int needed = t.length();
        int left = 0;
        int minLen = INT_MAX;

        for (int right = 0; right < s.length(); ++right) {
            char ch = s[right];
            
            if (map.count(ch)) {
                if (map[ch] > 0) {
                    count++;
                }
                map[ch]--;
            }

            // **Shrink** the window while it is valid
            while (count == needed) {
                // Update result
                if (minLen > right - left + 1) {
                    minLen = right - left + 1;
                    start = left;
                }
                
                char leftChar = s[left];
                if (map.count(leftChar)) {
                    map[leftChar]++;
                    if (map[leftChar] > 0) {
                        count--;
                    }
                }
                left++;
            }
        }

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