Minimum Window Substring

LeetCode

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Initial attempt

Time spent: 53m | Runtime: 62.63% | Memory: 28.37%

• It was difficult to make heads or tails of this problem initially. After staring at it for 25 minutes, I looked at the solution. It still took 28 minutes after that to produce an answer.
• The performance numbers aren't accurate since it's based on a solution that I read, though the code was my own.
• Sliding windows wasn't on my radar when I did this.

Solution

• Count characters in t.
• Iterate through s until a substring starting at 0 includes everything in t.
• Slide this window to be as small as it can be as it shifts towards the end of s.

Cleaned up code

Time spent: 26m | Runtime: 22.41% | Memory: 10.46%

import collections

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        missing_t = collections.Counter(t)
        t_count = collections.Counter(t)

        start = 0
        window_count = collections.defaultdict(int)
        min_found = ''
        for end, end_char in enumerate(s):
            window_count[end_char] += 1

            if missing_t:
                if end_char in missing_t:
                    missing_t[end_char] -= 1
                    if missing_t[end_char] == 0:
                        del missing_t[end_char]

            if not missing_t:
                while window_count[s[start]] > t_count[s[start]]:
                    window_count[s[start]] -= 1
                    start += 1
                if min_found == '' or len(min_found) > end - start + 1:
                    min_found = s[start:end + 1]

        return min_found