Minimum Window Substring

Problem Statement

Given two strings s and t, return the shortest substring of s such that every character in t, including duplicates, is present in the substring. If such a substring does not exist, return an empty string "".

You may assume that the correct output is always unique.

Example 1:

Input: s = "OUZODYXAZV", t = "XYZ"


Output: "YXAZ"

Explanation: "YXAZ" is the shortest substring that includes "X", "Y", and "Z" from string t.

Example 2:

Input: s = "xyz", t = "xyz"


Output: "xyz"

Example 3:

Input: s = "x", t = "xy"


Output: ""

Constraints:

  • 1 <= s.length <= 1000
  • 1 <= t.length <= 1000
  • s and t consist of uppercase and lowercase English letters.

You should aim for a solution with O(n) time and O(m) space, where n is the length of the string s and m is the number of unique characters in s and t.

You should aim for a solution with O(n) time and O(m) space, where n is the length of the string s and m is the number of unique characters in s and t.

Hint 1

A brute force solution would involve checking every substring of s against t and returning the minimum length valid substring. This would be an O(n^2) solution. Can you think of a better way? Maybe you should think in terms of frequency of characters.

Hint 2

We need to find substrings in s that should have at least the characters of t. We can use hash maps to maintain the frequencies of characters. It will be O(1) for lookups. Can you think of an algorithm now?

Hint 3

We can use a dynamically sized sliding window approach on s. We iterate through s while maintaining a window. If the current window contains at least the frequency of characters from t, we update the result and shrink the window until it is valid.

Hint 4

We should ensure that we maintain the result substring and only update it if we find a shorter valid substring. Additionally, we need to keep track of the result substring’s length so that we can return an empty string if no valid substring is found.

Solution

Brute Force

def min_window(s: str, t: str) -> str:
    if not t:
        return ""


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


    result, result_len = [-1, -1], float("infinity")
    for i in range(len(s)):
        count_s = {}
        for j in range(i, len(s)):
            count_s[s[j]] = 1 + count_s.get(s[j], 0)


            flag = True
            for c in count_t:
                if count_t[c] > count_s.get(c, 0):
                    flag = False
                    break


            if flag and (j - i + 1) < result_len:
                result_len = j - i + 1
                result = [i, j]


    l, r = result
    return s[l : r + 1] if result_len != float("infinity") else ""

Time complexity: O(n^2) Space complexity: O(m)

Sliding Window

def min_window(s: str, t: str) -> str:
    if not t:
        return ""


    count_t, window = {}, {}
    for c in t:
        count_t[c] = 1 + count_t.get(c, 0)


    have, need = 0, len(count_t)
    result, result_len = [-1, -1], float("infinity")
    left = 0
    for right in range(len(s)):
        c = s[right]
        window[c] = 1 + window.get(c, 0)


        if c in count_t and window[c] == count_t[c]:
            have += 1


        while have == need:
            if (right - left + 1) < result_len:
                result = [left, right]
                result_len = right - left + 1


            window[s[left]] -= 1
            if s[left] in count_t and window[s[left]] < count_t[s[left]]:
                have -= 1
            left += 1
    l, r = result
    return s[l : r + 1] if result_len != float("infinity") else ""

Time complexity: O(n) Space complexity: O(m)