Minimum Window Substring

The problem description can be found in LeetCode.

Approach

From the title we already know that we have a Sliding Window problem. In particular, this is a Sliding Window with a Dynamic Size problem.

In fact, the problem doesn't mention any static size to check, so we don't know about the actual size of the window.

The trick here is to find an efficient way to understand if the property of the window is fulfilled. In this case, we need to be sure that all the characters of t are in s (duplicates included).

An efficient way to do so is to keep track of the matching characters. Hence, we will try to shrink the window as soon as we have the same number of matching characters.

This value is simply equal to the size of the counter dictionary that we will create for the string t.

Solution

from collections import defaultdict
from typing import DefaultDict


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

        t_counter: DefaultDict[str, int] = self.get_chars_counter(t)
        required_chars = len(t_counter)

        left = 0
        matching_chars = 0
        s_counter: DefaultDict[str, int] = defaultdict(int)
        ans = ""

        for right, char in enumerate(s):
            # the current char is not in `t`
            # hence, we can avoid to consider it
            if char not in t_counter:
                continue

            s_counter[char] += 1
            # incrementing the `matching_chars` once the number of occurrences
            # for `char` is equal in both counters
            if s_counter[char] == t_counter[char]:
                matching_chars += 1

            # shrink if we have the same number of matching characters
            while left <= right and matching_chars == required_chars:
                left_char = s[left]
                win_size = right - left + 1
                # update the solution
                if not ans or win_size < len(ans):
                    ans = s[left : right + 1]

                # be sure that the `left_char` is in the `t` string,
                # otherwise we risk to consider unused chars
                if left_char in t_counter:
                    s_counter[left_char] -= 1
                    # decrease the `matching_chars` once `s_counter`
                    # does not contain enough for matching `t`
                    if s_counter[left_char] < t_counter[left_char]:
                        matching_chars -= 1

                left += 1

        return ans

    def get_chars_counter(self, s: str) -> DefaultDict[str, int]:
        counter: DefaultDict[str, int] = defaultdict(int)

        for char in s:
            counter[char] += 1

        return counter

Complexity

• Time: $O(m+n)$
• Space: $O(1)$

Where $m$ and $n$ are the size of the strings $s$ and $t$, respectively. Regarding the space, the alphabet is limited to 56 characters, therefore it is constant.