class Solution:
    '''
    Time Complexity: O(|s| + |t|) where |s| and |t| are the lengths of strings s and t respectively.
    Space Complexity: O(1) assuming, output array is not considered.
    '''
    def minWindow(self, s: str, t: str) -> str:
        if len(t) > len(s):
            return ""
        need = Counter(t)
        have = Counter(s)
        for c in need:
            if need[c] > have.get(c, 0):
                return ""

        have = dict()
        needCount = len(t)
        minL, minR = 0, len(s)
        l = 0

        for r, c in enumerate(s):
            amount = have.get(c, 0)
            have[c] = amount + 1
            if c in need and amount < need[c]:
                needCount -= 1
            if needCount == 0:
                while l < r:
                    if s[l] in need and have[s[l]] <= need[s[l]]:
                        break
                    have[s[l]] = have[s[l]] - 1
                    l += 1

                if r+1 - l < minR - minL:
                    minR = r+1
                    minL = l
        return s[minL:minR]

// // Similar logic but is quicker because of using arrays as hashmaps
public String minWindow2(String s, String t) {
    if (t.length() > s.length()) {return "";}
    int[] need = new int[256];
    int[] window = new int[256];

    for (char c : t.toCharArray()) {
        need[c]++;
    }

    int left = 0;
    int right = 0;
    int minLen = s.length() + 1;
    int minLeft = 0;

    int count = 0;

    while (right < s.length()) {
        char rightChar = s.charAt(right);
        window[rightChar]++;

        if (window[rightChar] <= need[rightChar]) {
            count++;
        }

        while (count == t.length()) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minLeft = left;
            }

            char leftChar = s.charAt(left);
            window[leftChar]--;

            if (window[leftChar] < need[leftChar]) {
                count--;
            }

            left++;
        }

        right++;
    }

    if (minLen == s.length() + 1) {
        return "";
    }

    return s.substring(minLeft, minLeft + minLen);
}

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(t) > len(s):
            return ""
        
        oStart = 0
        oEnd = len(s) + len(t)
        freq = Counter(t)
        need = len(freq)
        available = defaultdict(int)
        important = []
        i = 0
        
        for end,c in enumerate(s):
            if c in freq:
                important.append(end)
                available[c] += 1
                if available[c] == freq[c]:
                    need -= 1
                if need == 0:
                    while important[i] < end and available[s[important[i]]] > freq[s[important[i]]]:
                        available[s[important[i]]] -= 1
                        i+=1
                    if oEnd-oStart > end-important[i]:
                        oEnd = end
                        oStart = important[i]
                    available[s[important[i]]] -= 1
                    i+=1
                    need += 1
        
        return s[oStart: oEnd+1] if oEnd != len(s) + len(t) else ""

public String minWindow(String s, String t) {
    if (t.length() > s.length()) { return ""; }
    int need = 0, have = 0, i = 0, oi = 0, oj = s.length()+t.length();
    Map<Character, Integer> want = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    List<Integer> indices = new ArrayList<>();

    for (char c: t.toCharArray()) {
        want.put(c, want.getOrDefault(c,0) + 1);
    }
    need = want.size();

    for (int k=0; k<s.length(); k++) {
        char c = s.charAt(k);
        if (want.containsKey(c)) {
            indices.add(k);
            window.put(c, window.getOrDefault(c, 0) + 1 );
            if (window.get(c).equals(want.get(c))) {
                have++;
            }
            if (need == have) {
                while (indices.get(i) < k && window.get(s.charAt(indices.get(i))) > want.get(s.charAt(indices.get(i))) ) {
                    c = s.charAt(indices.get(i));
                    window.put(c ,window.get(c)-1);
                    i++;
                }
                if (oj-oi > k-indices.get(i)) {
                    oj = k;
                    oi = indices.get(i);
                }
                c = s.charAt(indices.get(i));
                window.put(c,window.get(c)-1);
                have--;
                i++;
            }
        }
    }

    if (oj == s.length()+t.length()) {
        return "";
    }
    return s.substring(oi,oj+1);
}