Minimum Window Substring

Q: What is the time complexity of Minimum Window Substring?

The missing-counter window runs in O(n + m) time, where n and m are the lengths of s and t . Building the table reads t once, and each character of s enters and leaves the window at most once. The extra memory is one count per character code.

Q: How is Minimum Window Substring different from finding an anagram in a string?

An anagram holds exactly the letters of t , so its window has a fixed length m and slides one step at a time. Here extra characters are allowed, so the length is part of the answer: the window grows until it covers t and shrinks while it still does.

HardSliding window Hashing

+10

You get two strings, s and t. Find the shortest substring of s that contains every character of t, counting repeats: if t holds a letter twice, the substring must hold it at least twice. Order does not matter, and other characters may appear too.

If several substrings are shortest, return the leftmost. If none contains all of t, return an empty string.

Function

minWindow(s: string, t: string) → string

sstring: the string to search in
tstring: the characters the window must contain, with repeats
Returnsstring: the shortest, then leftmost, substring of s that contains all of t, or an empty string

Constraints

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ t.length ≤ 10⁴
s and t hold only English letters. Uppercase and lowercase letters are different characters.
When several substrings are shortest, the answer is the leftmost one; when none exists, it is "".

Examples

Input: s = "mappingtheplan"t = "nap"
Output: "plan"
Explanation: The first window from the left that holds an n, an a and a p is appin, five characters. plan holds all three in four, and no run of three does.

Input: s = "banana"t = "aan"
Output: "ana"
Explanation: t asks for two copies of a and one n. ana at index 1 holds exactly that. A second ana starts at index 3, and the leftmost one wins.

Input: s = "Coddy"t = "cd"
Output: ""
Explanation: The C in Coddy is uppercase, a different character from c. No substring holds a lowercase c, so the answer is the empty string.

Follow-up

When t uses few letters and s is long, most of s never matters. Can you make the window jump only between positions that hold a letter of t?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Only the counts in a window matter, not their order. Move the right edge until the window covers t, then the left edge while it still does; neither edge goes back. A counter of missing characters tells you in one step whether the window covers t.

Grow a window from every start

Correct, but does not finish on the largest tests

Intuition

Fix a start and grow the window one character at a time, keeping a count of each character. After every step, check each of the u letters t uses. The first end that passes gives the shortest covering window from this start, so stop there. Starts go left to right and only a strictly shorter window replaces the best, so ties keep the leftmost.

If no window exists, every start reads to the end of s: about n²/2 steps, 1.25 × 10^9 for n = 5 × 10^4.

Algorithm

Count the copies of each letter t asks for.
For every start, clear a count table and move end right, adding s[end].
When the window holds enough of every letter, keep it if it is strictly shorter than the best, and go to the next start.
Return the best window, or "" if none covered t.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    best_start, best_len = 0, len(s) + 1
    for start in range(len(s)):
        have = [0] * 128  # counts inside s[start..end]
        for end in range(start, len(s)):
            have[ord(s[end])] += 1
            if all(have[c] >= need[c] for c in letters):
                # The first end that covers t gives the shortest window from this start.
                if end - start + 1 < best_len:
                    best_start, best_len = start, end - start + 1
                break
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Sliding window that checks every letter

Intuition

Adding characters to a covering window keeps it covering, and removing characters from a window that misses something keeps it missing. So as the start moves right, the end of the shortest covering window never moves left.

No window is missed. Take the best window, from L to R. For left to pass L before right reaches R, a shorter window from L would have to cover t. So when right reaches R, shrinking walks left to L and records it.

Each edge moves at most n times, but each check reads up to u counts: O(n·u).

Algorithm

Count the copies t asks for; set left = 0 and the best length to n+1.
For each right, add s[right] to the window's counts.
While every letter of t has enough copies, record the window if it is strictly shorter, remove s[left] and move left forward.
Return the best window, or "" if the best length is still n+1.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    have = [0] * 128  # counts inside s[left..right]

    def covers():
        for c in letters:
            if have[c] < need[c]:
                return False
        return True

    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        have[ord(s[right])] += 1  # expand on the right
        while covers():  # shrink from the left while the window still covers t
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            have[ord(s[left])] -= 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Sliding window with a missing counter

Intuition

Replace the scan with one number. Let need[c] be the copies of c that t asks for minus the copies in the window; a negative value means spares. Let missing be the copies the window still lacks, starting at the length of t. The window covers t exactly when missing is 0.

A character that enters while its need is above 0 fills a gap, so missing drops. A character whose removal pushes need above 0 opens a gap, so missing rises. Spares never touch it. On banana with t = aan, missing first hits 0 at bana, and dropping the spare b leaves ana still covering.

Each character enters and leaves once at a fixed cost: O(n + m) time, with one table of 128 counts.

Algorithm

Fill need with the counts of t; set missing to the length of t, left = 0 and the best length to n+1.
For each right: if need[s[right]] is above 0, lower missing; then lower need[s[right]].
While missing is 0, record the window if it is strictly shorter. Raise need[s[left]]; if it is now above 0, raise missing. Move left forward.
Return the best window, or "" if the best length is still n+1.

def minWindow(s, t):
    # need[c]: copies of c that t asks for minus copies inside the window.
    # Positive means the window still lacks c; negative means it holds spares.
    need = [0] * 128
    for ch in t:
        need[ord(ch)] += 1
    missing = len(t)  # characters of t the window does not cover yet
    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        c = ord(s[right])
        if need[c] > 0:  # this copy fills a gap
            missing -= 1
        need[c] -= 1
        while missing == 0:  # the window covers t: record it, then shrink
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            c = ord(s[left])
            need[c] += 1
            if need[c] > 0:  # gave away a copy t needs
                missing += 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Pitfalls and edge cases

Counting letters instead of copies. t = aan needs two as, so ban does not cover it.
Changing missing for every character that enters or leaves. A spare a then counts, and missing can hit 0 while the window lacks the n.
Replacing the best window on an equal length. In the second example that returns the ana at index 3.
Using n as the "not found" length. When the answer is all of s, its length is n too; start from n+1.
A table of 26 slots indexed by c - 'a'. Uppercase letters, as in the third example, fall outside it.

Frequently asked questions3

What is the time complexity of Minimum Window Substring?

The missing-counter window runs in O(n + m) time, where n and m are the lengths of s and t. Building the table reads t once, and each character of s enters and leaves the window at most once. The extra memory is one count per character code.

Why does the left edge never move back?

The left edge passes a position only after the window starting there has covered t, and that window was the shortest covering one from that start. Any window from there that ends later is longer, so going back can never find a better answer.

How is Minimum Window Substring different from finding an anagram in a string?

An anagram holds exactly the letters of t, so its window has a fixed length m and slides one step at a time. Here extra characters are allowed, so the length is part of the answer: the window grows until it covers t and shrinks while it still does.

def minWindow(s, t):
    # Write code here

Test #1

Test #2

Test #3

Arguments

s = "mappingtheplan"
t = "nap"

Expected Output

"plan"

Minimum Window Substring

Function

Constraints

Examples

Hints

Solution

Grow a window from every start

Sliding window that checks every letter

Sliding window with a missing counter

Pitfalls and edge cases

Frequently asked questions3

Similar problems