HardHash TableStringSliding Window

Minimum Window Substring

1 approach, code in every language

You are given two strings s and t. Find the shortest contiguous substring of s that contains every character of t, counting duplicates. In other words, if a character appears multiple times in t, the chosen window must contain it at least that many times.

Return that minimum-length substring. If s has no window that covers all of t, return the empty string "".

The answer is guaranteed to be unique when it exists.

Example 1

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

Output: "BANC"

The substring "BANC" contains one A, one B, and one C, and no shorter window of s covers all three.

Example 2

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

Output: "a"

The entire string is the only window, and it already contains the required character.

Constraints

m == s.length
n == t.length
1 <= m, n <= 10^5
s and t consist of uppercase and lowercase English letters.

Expand-Then-Contract Sliding Window

Grow the window to the right until it satisfies all character requirements, then shrink it from the left to find the tightest valid window.

Loading animation…

Intuition

We keep a frequency map of exactly what characters t demands and how many of each. As a right pointer expands the window, we increase the counts of characters we have collected and maintain a match counter that tracks how many distinct requirements are fully satisfied. The moment every requirement is met, the window is valid, so we try to shorten it by advancing a left pointer, giving back characters until some requirement is no longer satisfied. Every time the window is valid we compare its length with the best seen and record the smallest. Because each pointer only moves forward, the whole scan is linear.

Algorithm walkthrough

1Build a need map from t: the count of each required character, and set required to the number of distinct characters.
2Expand the right pointer one character at a time, incrementing that character's count in the window map.
3Whenever a character's window count reaches its needed count, increment have; when have equals required the window covers all of t.
4While the window is valid, record it if it is shorter than the best window found so far, then move the left pointer forward and decrement the leaving character's count.
5If dropping the leaving character makes its count fall below what is needed, decrement have so the window becomes invalid again and expansion resumes.
6After the right pointer reaches the end, return the recorded best window, or "" if none was ever valid.

Implementation

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        need = {}
        for c in t:
            need[c] = need.get(c, 0) + 1
        required = len(need)
        window = {}
        have = 0
        best_len = float("inf")
        best_left = 0
        left = 0
        for right, c in enumerate(s):
            window[c] = window.get(c, 0) + 1
            if c in need and window[c] == need[c]:
                have += 1
            while have == required:
                if right - left + 1 < best_len:
                    best_len = right - left + 1
                    best_left = left
                lc = s[left]
                window[lc] -= 1
                if lc in need and window[lc] < need[lc]:
                    have -= 1
                left += 1
        return "" if best_len == float("inf") else s[best_left:best_left + best_len]

Time

O(m + n)

Space

O(k)

Each pointer traverses s once. Space is bounded by the number of distinct characters (at most a fixed alphabet).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Shortest Kit Stretch is our own problem on the technique behind Minimum Window Substring: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free