This is a solution of leetcode 76. Minimum Window Substring.

Analysis

The target here is to find the shortest substring of a given string $s$ which contains all the letters we need (including duplicates) to spell another string $t$.

It is pretty easy to solve this question by brutal force. You can use a double loop to list all the slices of the string, check if it matches the requirements, and write down the shortest one. The time complexity would be $O(n^2)$. Here $n$ denotes the length of string $s$.

To speed up, we can use a sliding window approach. That is using a left pointer and a right pointer to denote the start and the end of a substring separately. As the right pointer expands the window and the left pointer shrinks the window, we can find all the possible substrings we need. The time complexity would be $O(n+n)=O(n)$ because the left pointer and the right pointer both visit all the indices of the string only once.

Till now, we have managed to list all the possible substrings efficiently. However, we need to compare a substring with the target string to make sure that we have enough letters in the substring to compose the target string. The plainest way would be to retrieve all the letters in the substring and remove them from the target string. In the end, if the target string is empty, the substring is a possible answer. Suppose the length of the substring is $l_1$, and the length of the target string is $l$, the time complexity here would be $O(l_1*l)$.

To speed this up, we can use a dictionary to remember all the characters that exist in the target string and record their count as the value. And use another dictionary to keep tracking all the characters and their count in the sliding window. You just need to maintain this dictionary while you expand or shrink the window. To check if we have a qualified substring, we only need to retrieve all the letters in the former dictionary and make sure they are in the latter one and the count of this letter is less than or equal to that in the latter. This time complexity would be $O(C)$, where $C$ denotes the count of the unique letters in the target string, which is obviously less than or equal to the length $l$ of it.

By now we have got the final approach, and we can write the code.

Code

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = dict()
        # need stores the letters in t and their count
        for c in t:
            if c not in need:
                need[c] = 0
            need[c] += 1
        res = [0, float('inf')]
        # res stores the temporary answer
        left, right = 0, 0
        while right < len(s):
            c = s[right]
            if c in need:
                need[c] -= 1
            enough_letters_flag = all([need[k] <= 0 for k in need])
            if enough_letters_flag:
                while left < right and (s[left] not in need or (s[left] in need and need[s[left]] < 0)):
                    if s[left] in need:
                        need[s[left]] += 1
                    left += 1
                if right - left < res[1] - res[0]:
                    res = [left,right]
                need[s[left]]+=1
                left += 1
            right += 1
        return '' if isinstance(res[1],float) else s[res[0]:res[1]+1]