Minimum Window Substring

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

The sliding window with a missing counter 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, at a fixed cost per move. The extra memory is a table with one count per character code, which does not grow with the input.

Q: What does the missing counter count?

It is the number of character copies t asks for that the window does not hold yet, the sum of the positive values in need . It starts at the length of t and is 0 exactly when the window covers t . Spare copies never change it, which is what lets one comparison replace a scan over every letter.

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

An anagram has exactly the letters of t and no others, so the window has a fixed length of m and slides one step at a time. Here the window may hold extra characters, so its length is part of the answer: it grows on the right until it covers t and shrinks on the left while it still does.

HardSliding window Hashing

+10

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

If several substrings share the shortest length, return the leftmost one. If no substring of s 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: Reading from the left, the first window that holds an n, an a and a p is appin, five characters long. plan at the end holds all three in four characters, and no run of three characters 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 only C in Coddy is uppercase, and uppercase and lowercase letters are different characters. No substring holds a lowercase c, so the answer is the empty string.

+17 hidden tests on Submit

Follow-up

When t uses only a few letters and s is long, most of s can never matter. Can you make the window jump only between the 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

The answer depends on how many of each character a window holds, not on their order, and the best window can start anywhere. Trying every start with every end means O(n²) windows. What cracks it is a window whose edges only move forward: the right edge grows it until it covers t, the left edge shrinks it while it still does, and one counter of missing characters tells you in a single step whether it covers t.

Grow a window from every start

Correct, but does not finish on the largest tests

Intuition

Fix where the substring starts. Then grow it one character at a time, keeping a count of each character inside, and after every step check whether it covers t: for each of the u different letters t uses, the window must hold at least as many copies as t does. The first end that passes gives the shortest covering window for this start, because every shorter one from the same start was checked first and failed. Stop there.

Do that for every start and keep the shortest window. Starts are tried from left to right and a window replaces the best one only when it is strictly shorter, so among equally short windows the leftmost one stays.

It is slow when windows are long or missing. If the only Z in s sits at the very end and t asks for one, every start reads all the way to the end: about n²/2 steps, which is 1.25 × 10^9 for n = 5 × 10^4, each with a check over up to 52 letters. The same happens when no window exists at all.

Algorithm

Count how many copies of each character t asks for, and list the letters it uses.
For every start, clear a table of counts and move end from start to the end of s, adding s[end] to the table.
After each addition, check every letter of t. If the window holds enough of each, compare its length with the best so far, keep it if it is strictly shorter, and stop growing.
After all starts, 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

Two facts remove the restart. Adding characters to a window that covers t keeps it covering, and removing characters from a window that misses something keeps it missing. So when the start moves right, the end of the shortest covering window can only stay or move right. Both edges can sweep forward together, and neither ever goes back.

Move right over s, adding each character to a table of counts. Whenever the window covers t, it is a candidate: record it if it is shorter than the best, then remove s[left] and move left forward, and check again. Repeat until the window stops covering t, then go back to growing on the right.

No window is missed. Take the best window, from L to R. If left had passed L before right reached R, some window from L ending before R would have covered t, and it would be shorter than the best. So when right reaches R, the shrinking loop walks left up to L and records the best window. Each edge moves at most n times, but every check reads up to u counts, one for each letter t uses, even though only one count changed since the last check.

Algorithm

Count the copies t asks for and list its letters; start with an empty window, left = 0, and a best length of n+1.
Move right over every index and add s[right] to the window's counts.
While every letter of t has enough copies in the window, record the window if it is strictly shorter than the best, remove s[left] from the counts 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

Keep the same window and replace the check with one number. Let need[c] be the copies of c that t asks for minus the copies inside the window. A positive value means the window still lacks some, a negative one means it holds spares. Let missing be the total number of copies the window lacks, which starts at the length of t. The window covers t exactly when missing is 0.

Updating it costs one step. When s[right] enters and need for it is above 0, it fills a gap, so missing drops by one; either way need drops by one, and it may go below 0 as a spare. When s[left] leaves, need rises by one, and if it is now above 0 the window gave away a copy t needed, so missing rises by one. Spares come and go without touching missing.

Trace s = banana, t = aan: need starts at a 2, n 1 and missing at 3. b is not needed. The first a brings missing to 2, the n to 1, the second a to 0, so bana covers t. Shrinking drops the spare b and leaves ana, three characters, the new best. Dropping that a sets missing back to 1. The last a covers again with nana, which shrinks to the second ana. It is not shorter, so the leftmost ana stays.

Each character of s enters the window once and leaves at most once, and each move costs a fixed amount of work. Building need reads t once. The whole run is O(n + m), with a table of 128 counts as the only extra memory.

Algorithm

Fill need with the counts of t, and 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 than the best. Then 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

Most wrong answers count the wrong thing or record the window at the wrong moment.

Counting letters instead of copies. t = aan needs two as, so ban does not cover it.
Lowering missing for every character that enters. A third a is a spare; if it lowers missing, the counter reaches 0 while the window still lacks the n. Lower it only when need was above 0.
Raising missing for every character that leaves. Dropping a spare keeps the window covering t; raise it only when need goes above 0.
Recording the window after the shrinking loop. By then it no longer covers t. Record it inside the loop, before you remove s[left].
Replacing the best window when the new one is equally long. That returns the rightmost of the shortest windows; compare with a strict less than.
Using n as the "not found" length. When the answer is all of s, its length is n too. Start from n+1 so the two cases differ.
A table of 26 slots indexed by c - 'a'. Uppercase letters fall outside it. Use one slot per character code.

Frequently asked questions4

What is the time complexity of Minimum Window Substring?

The sliding window with a missing counter 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, at a fixed cost per move. The extra memory is a table with one count per character code, which does not grow with the input.

Why does the left edge never move back?

The left edge moves past a position only after a window starting there has covered t, and that was the shortest covering window from that start. Any window that starts there and ends later is longer, so going back could never find a better answer. That is why both edges sweep forward once and the work stays linear.

What does the missing counter count?

It is the number of character copies t asks for that the window does not hold yet, the sum of the positive values in need. It starts at the length of t and is 0 exactly when the window covers t. Spare copies never change it, which is what lets one comparison replace a scan over every letter.

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

An anagram has exactly the letters of t and no others, so the window has a fixed length of m and slides one step at a time. Here the window may hold extra characters, so its length is part of the answer: it grows on the right until it covers t and shrinks on the left while it still does.

Python

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

Test cases

Case 1

Case 2

Case 3

Input

s = "mappingtheplan"
t = "nap"

Expected

"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 questions4

Similar problems