LC 76 - Minimum Window Substring

Question

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.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"

Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""

Explanation: Both ‘a’s from t must be included in the window.
Since the largest window of s only has one ‘a’, return empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Links

Question here and solution here

Solution

concept

We keep track of 2 dictionary, one each for the char counter for s and t.
The number of unique char in t is the number of conditions we have to be met (need) for the window in s. So we can keep track if have == need each time there is a update in the counter.
We use a sliding window: we keep expanding the window (move r) until the window is valid have == need, and we shrink the window (move l) until the window is not valid.
We will minimise the window length along the way to find out what is the minimum window in the end.

code

class NeetSolution(object):
    def minWindow(self, s, t):
        """
        space complexity = O(n) where n is the length of s
        use a sliding window to find the shortest substring that contains all the characters in t
        keep track of the frequency of the characters in t and the frequency of the characters in the window
        also take note how many conditions or unique char with the minimum required frequency met
        """
        count_t = {}
        count_window = {}

        for char in t:
            count_t[char] = 1 + count_t.get(char, 0)

        result_index = [-1, -1]
        result_len = float("infinity")
        # window in s has how many char with the minimum char frequency met in str t
        have = 0 
        # str t's unique char frequency count, determines the number of condition needs to be met
        need = len(count_t)

        l = 0
        for r in range(len(s)):
            count_window[s[r]] = 1 + count_window.get(s[r], 0)

            if s[r] in count_t and count_window[s[r]] == count_t[s[r]]:
                # the preivous r movement makes the substr just met one of the requirement
                have += 1

            # if the condition is met, we want to keep move l pointer to find valid substr
            # that met all conditions
            while have == need:
                # update our shortest result
                if (r - l + 1) < result_len:
                    result_index = [l, r]
                    result_len = r - l + 1
                # pop the left from the window
                count_window[s[l]] -= 1
                # if the left pointer movement made one of the condition not hold
                if s[l] in count_t and count_window[s[l]] < count_t[s[l]]:
                    have -= 1
                l += 1

        return s[result_index[0]:result_index[1]+1] if result_len != float("infinity") else ""

Complexity

time: $O(n)$
space: $O(m)$
Where $n$ is the length of the string s and $m$ is the total number of unique characters in the strings t and s.