Problem statement

https://leetcode.com/problems/minimum-window-substring/

Solution

The idea of sliding window with 2 pointers: we create counter cnt_t is frequencies how many time s we need to take each symbol, for example for abca we have a:2, b:1, c:1. We create also cnt_s as empty counter, which will keep information about frequencies is current window [beg, end) - not that we do not include end. To quickly understand how many symbols have good frequency, we have found variable. Now, we can have two options to change our window:

  1. If found == len(cnt_t), it means that we have in our window all symbols we want: no need to extend it to the right: we will shrink it to the left. We need to update our ans, where we keep pair (end - beg, beg) , then we look at the first element old = s[beg] and if we have cnt_s[old] == cnt_t[old] it means that we have exactly the right frequency for this symbol. So, when we move beg one position to the right, we need to decrease found by one. Finally, we decrease frequency by one and more beg` to the right.
  2. In the opposite case, first we check if end == len(s) and if it is true, we break. Then we look at the new symbol new = s[end] (because it was not included, windows are [beg, end). We check if cnt_s[new] == cnt_t[new] - 1 and if it is the case, it means, that when we add new symbol we need to increase found by one. Then we increase frequency and move end one position to the right.

Complexity

Time complexity is O(m + n), becuse on each step we move beg or end one point to the right. Space complexity is O(A), where A is the size of alphabet.

Code

class Solution:
    def minWindow(self, s, t):
        beg, end = 0, 0
        ans, found = (float("inf"), 0), 0
        cnt_t, cnt_s = Counter(t), Counter()
        while end <= len(s):
            if found == len(cnt_t):
                ans = min(ans, (end - beg, 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 s[ans[1]:ans[0]+ans[1]] if ans[0] != float("inf") else ""