Problem statement

https://binarysearch.com/problems/Minimum-Window-Substring/

Solution

Equal to Leetcode 0076. Minimum Window Substring

Complexity

It is O(m + n) for time and O(A) for space.

Code

class Solution:
    def solve(self, s, t):
        beg, end = 0, 0
        ans, found = float("inf"), 0
        cnt_t, cnt_s = Counter(t), Counter()
        while end <= len(s):
            if found == len(cnt_t):
                ans = min(ans, end - beg)
                old = s[beg]
                if cnt_s[old] == cnt_t[old]: found -= 1
                cnt_s[old] -= 1
                beg += 1
            else:
                if end == len(s): break
                new = s[end]
                if cnt_s[new] == cnt_t[new] - 1: found += 1
                cnt_s[new] += 1
                end += 1
        
        return ans if ans != float("inf") else -1