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

  • Brute Force: $O(n^2)$

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # count the characters in t
        c = Counter(t)
        # the smallest string that contains all characters in t
        smallest = ""

        # iterate over all characters in s
        for i in range(len(s)):
            # dictionary to keep track of all characters 
            # along with their required frequencies
            d = c.copy()

            # iterate over all characters in s
            # starting from `i`
            for j in range(i, len(s)):
                # the current character
                char = s[j]

                # check if we need to count 
                # this character towards 
                # the frequency requirement
                if char in d:
                    # decrement the frequency requirement
                    # of this character
                    d[char] -= 1
                    # remove the character from the dictionary
                    # if the frequency requirement is met
                    if d[char] == 0:
                        del d[char]
            # if the dictionary is empty
            # all frequencies requirements are met
            if not d:
                # this window will be smaller than the previous one
                # so we update the smallest string
                smallest = s[i : j + 1]

        # return the smallest string
        return smallest
  • Optimised Solution: $O(n)$

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # count the characters in t
        c = Counter(t)

        # number of unique characters in t
        # that we need to fully match
        requiredToFullyMatch = len(c.keys())

        # dictionary to keep track of the characters in the current window
        d = Counter()

        # the smallest window that contains all characters in t
        # so far
        smallest = ""

        # number of characters in the current window
        # that are fully matched
        fullyMatched = 0

        # left pointer
        l = 0

        # right pointer and the character pointed by it
        for r, char in enumerate(s):

            # update the current dictionary
            # with relevant character frequency
            d[char] = d.get(char, 0) + 1

            # check if the character is in t
            if char in c:
                # check if the character is fully matched
                # but not overmatched!
                if d[char] == c[char]:
                    # then we update fullyMatched
                    # by 1
                    fullyMatched += 1

            # compaction + udpate answer
            #
            # d is non-empty
            # and all characters in t are fully matched
            while d and fullyMatched == requiredToFullyMatch:
                # char pointer by left pointer
                leftChar = s[l]

                # update smallest string
                if r - l + 1 < len(smallest) or len(smallest) == 0:
                    smallest = s[l : r + 1]

                # compaction
                #
                # attempt to shrink the window
                # from the left
                if leftChar in d:
                    # remove the left character
                    # from the currrent window
                    d[leftChar] -= 1
                    # if the character is no longer fully matched
                    if leftChar in c and d[leftChar] < c[leftChar]:
                        # decrement fullyMatched by 1
                        fullyMatched -= 1

                # move left pointer forward by 1
                l += 1

                # if l has moved ahead of r
                if l > r:
                    # stop compaction
                    break

        # return smallest string
        return smallest

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 fullyMatched. Huge difference in speed. Oof.

And we are done.