Hard

Minimum Window Substring

LAB

Return the shortest substring of s containing every character of t with multiplicity. Return an empty string if none exists.

EXAMPLES

Example 1

Input
{
  "s": "ADOBECODEBANC",
  "t": "ABC"
}

Output
"BANC"

FUNCTION SHAPE

s: stringt: string→string

SOLUTION NOTE

This is a really hard problem. The optimized solution removes the window counter and just updates freq_small, along with an integer counter that records how many characters in small we currently have in our window. This shaves our subset check() in the while loop from O(26) to O(1).

Reveal reference solution +

pythonREFERENCE

# Naive O(26*m + n) solution
def minWindow(self, big: str, small: str) -> str:
    m, n = len(big), len(small)
    freq_small = Counter(small)
    window_freq = Counter()
    l = 0
    min_length = inf
    res = []

    def check(f1, f2):
        for b in f2:
            if f1[b] < f2[b]: return False
        return True

    for r in range(m):
        if big[r] in freq_small:
            window_freq[big[r]] += 1

        while check(window_freq, freq_small):
            if r - l + 1 < min_length:
                res = [l, r]
                min_length = r - l + 1

            if big[l] in freq_small:
                window_freq[big[l]] -= 1
            l += 1

    return big[res[0]:res[1]+1] if res else ""

# Optimized O(m+n) solution - INTERVIEW READY
def minWindow(self, big: str, small: str) -> str:
    m, n = len(big), len(small)
    freq_small = Counter(small)
    l = 0
    counter = 0
    min_length = inf
    res = []

    for r in range(m):
        if big[r] in freq_small:
            freq_small[big[r]] -= 1
            if freq_small[big[r]] >= 0:
                counter += 1

        while counter == n:
            if r - l + 1 < min_length:
                res = [l, r]
                min_length = r - l + 1

            if big[l] in freq_small:
                freq_small[big[l]] += 1
                if freq_small[big[l]] > 0:
                    counter -= 1
            l += 1

    return big[res[0]:res[1]+1] if res else ""

TimeO(m+n)

SpaceO(26) = O(1)

Open on LeetCode ↗