Minimum Window Substring LeetCode solution in Python

1
# Added on 2022-08-18 15:51:55.963915
2

3
var minWindow = function(s, t) {
4
    const tf = {}, sf = {};
5
    for(let c of t) {
6
        tf[c] = (tf[c] || 0) + 1;
7
    }
8
    let l = 0, r = 0, rs = t.length;
9
    let ml = -1, mr = -1;
10
    for(; r < s.length; r++) {
11
        const c = s[r];
12

13
        if(!tf[c]) continue;
14

15
        const sc = sf[c] || 0;
16
        sf[c] = sc + 1;
17
        if(sf[c] <= tf[c]) {
18
            rs--;
19
        }
20

21
        if(rs == 0) {
22
            while(true) {
23
                if(mr == -1 || mr - ml > r - l) {
24
                    [mr, ml] = [r, l];
25
                }
26

27
                const c = s[l];
28
                if(!tf[c]) {
29
                    l++;
30
                }
31
                else if(sf[c] - 1 < tf[c]) {
32
                    sf[c]--, l++, rs++;
33
                    break;
34
                } else {
35
                    sf[c]--;
36
                    l++;
37
                }
38
            }
39
        }
40
    }
41
    if(mr == -1) return '';
42
    return s.slice(ml, mr + 1);
43
};