Problem Statement in English

You’re give 2 strings, s and t. You need to find the minimum window in s which will contain all the characters in t.

If no such window exists in s, that covers all characters in t, return "".

If there are multiple such windows, you are required to return the smallest one.

Approach

The way I like to think about this is to first find the first window that contains all the characters in t. Then, we try to shrink the window from the left side, while maintaining the condition that all characters in t are still present in the window.

Next we do what I like to call compaction.

We keep shrinking the window from the left until we reach a stage where the current window doens’t contain everything in t. We then move the right pointer ahead by $1$ step, and try to find the next window that contains all characters in t, and again run compaction on it.

It’s important that we check if the compacted window is smaller than the current smallest window, and update the smallest window accordingly at every reduction.

Solution in Python


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t or len(s) < len(t):
            return ""

        target = Counter(t)
        current = defaultdict(int)
        
        have, need = 0, len(target)
        
        res, res_len = "", float("inf")
        l = 0

        for r, c in enumerate(s):
            if c in target:
                current[c] += 1
                if current[c] == target[c]:
                    have += 1

            while have == need:
                if (r - l + 1) < res_len:
                    res_len = r - l + 1
                    res = s[l:r + 1]

                left_char = s[l]
                if left_char in target:
                    current[left_char] -= 1
                    if current[left_char] < target[left_char]:
                        have -= 1
                l += 1

        return res

Complexity

  • Time: $O(n)$
    Since we only process $n$ elements at most.

  • Space: $O(1)$
    Since we only use a few integer variables.

Mistakes I Made

I was using dictionary comparison instead of maintaining doing a constant time check. Huge difference in speed. Oof.

And we are done.