DSA sheet · Strings · Sliding Window pattern

Minimum Window Substring

LeetCode marks this one Hard, but the teacher's promise is that, taught step by step, it feels like an easy-medium. She builds it in three stages: a brute force (every start, a window map, and a "does it cover t?" check), a sliding window with two maps plus a count of characters still needed, and finally the same window with only one map, which saves space.

Why it matters: this is the classic "shortest valid window" problem. Longest-window problems shrink only when the window breaks. Here it's the opposite: we shrink while the window is still valid, to squeeze it as small as possible. On top of her method, this page also covers the common formed / required way of writing the counter, which you'll see in many editorials.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (sliding window from scratch)
• Part A · Brute force: every start + a window map + a cover check
• Part B · Sliding window with two maps + a "still needed" count (her main method)
• Part C · The same window with a formed / required counter
• Part D · Space-optimised: one map with negative counts
• Part E · Revision page

Part 0 · Before starting

Substring = a contiguous piece

A substring is a piece of the string with no gaps: choose a start and an end and take everything between. (For arrays it's a subarray.) A string of length n has n·(n+1)/2 non-empty substrings, so trying them all is O(n²).

Brute force over all windows, and why it repeats work

Two loops: every start i, every end j. When i moves one step, the inner loop rebuilds and re-checks characters the previous round already processed. Sliding window keeps the current window and only adjusts its two edges.

The window [left..right], expanding and shrinking

• Expand: right moves forward and the new character is added to our bookkeeping.
• Shrink: left moves forward and the character at left is removed.

The teacher's rule again: right is responsible for expanding, left for shrinking, and left undoes exactly what right did. Both only move forward. Length = right − left + 1.

Fixed-size vs variable-size

Longest vs shortest vs count: when do we shrink?

(For "count with exactly K", there's also the exactly(K) = atMost(K) − atMost(K−1) trick. Not needed here.)

Why sliding window works here (the monotonic rule)

"The window covers t" means every character of t is inside, with at least the same number of copies. Adding a character can never break coverage. Removing one can only keep it or break it. So:

• if [left..right] covers t, every bigger window around it also covers t (but it's longer, so it's useless to us);
• if [left..right] doesn't cover t, every smaller window inside it doesn't either.

That one-way behaviour is what lets both pointers move only forward. (Sum problems lose it when numbers can be negative, which is why those need a different pattern.)

Frequency maps (Counter)

A frequency map stores character → how many times. In Python, collections.Counter(t) builds it in one line: Counter("AABC") = {A:2, B:1, C:1}. For coverage we compare counts with "at least": window[c] ≥ need[c] for every c in t. Extra copies, and extra characters that aren't in t, are allowed.

def shortest_valid(s, add, remove, is_valid):
    left = 0
    best_len, best_left = float('inf'), 0
    for right in range(len(s)):
        add(s[right])                       # expand
        while is_valid():                   # valid -> try to make it smaller
            if right - left + 1 < best_len:
                best_len, best_left = right - left + 1, left
            remove(s[left])                 # shrink
            left += 1
    return "" if best_len == float('inf') else s[best_left:best_left + best_len]

Part A · Brute force: every start + a cover check

LeetCode 76

1The question in simple words

You get two strings, s (length m) and t (length n). Return the shortest substring of s that contains every character of t, duplicates included. Other characters may also be inside. If no such substring exists, return the empty string "".

"ADOBEC" (index 0..5) also contains A, B and C, but its length is 6. "BANC" has length 4, the shortest. "Duplicates included" means that if t = "AA", the window needs two A's. LeetCode's other examples: s = "a", t = "a" → "a", and s = "a", t = "aa" → "" (only one a exists).

2What the constraints tell us

• m, n up to 10⁵. O(n²) = 10¹⁰, far past ~10⁸ → brute force will TLE. We need about O(m + n).
• s and t hold upper- and lower-case letters. In general, the teacher counts the possible characters as up to 256 (lower case, upper case, symbols). That bounds the size of any map: it's a constant.
• t can be longer than s → then no window can cover it → "".

3Intuition: grow from each start until it covers t

First build tMap, the count of each character in t. Then fix a start i, grow j, and keep a window map of s[i..j]. After each new character, ask: "does the window map have at least as many of each character as tMap?" The first j where the answer is yes gives the shortest valid window for this start. Going further only makes it longer, so we break and move i.

4Building the logic from the example

i = 0

tMap = {A:1, B:1, C:1}. "A" → has A, no B or C. "AD", "ADO", "ADOB" (A, B ✓, C missing), "ADOBE", then "ADOBEC" → A, B and C all there ✓. Length 6, our first answer.

i = 1

Fresh window map. "D", "DO", "DOB", "DOBE", "DOBEC" (B, C ✓, no A), "DOBECO", "DOBECOD", "DOBECODE", "DOBECODEB", "DOBECODEBA" → now A is in too ✓. The window holds B twice while t needs it once.

i = 2 and onwards

Same thing: from index 2 the first covering window is "OBECODEBA" (9). And so on. The shortest one appears from i = 9: "BANC" (4).

The cover check (her isValid / match function)

Loop over every character c of tMap. If the window has fewer c's than tMap needs (e.g. t needs B:3 but the window has B:2), return False. If every character passes, return True.

Updating the answer

Update when the new valid window is shorter than the stored one. The teacher points out a trap: if the answer starts as the empty string "", then "shorter than the answer" means shorter than length 0, which never happens. So the first valid window must be accepted when the answer is still empty. (In code below, we keep a best length that starts at infinity, which avoids the trap.)

5Approach steps

1. Build need = Counter(t).
2. For each start i: empty window map.
3. For j from i: add s[j] to the window.
4. If the window covers need: if j − i + 1 is shorter than the best, save it. Break.
5. Return the best substring, or "".

6Code (Python)

from collections import Counter

class Solution:
    def minWindow(self, s, t):
        need = Counter(t)                       # tMap
        best_len, best_left = float('inf'), 0
        for i in range(len(s)):
            window = {}                         # sMap for s[i..j]
            for j in range(i, len(s)):
                window[s[j]] = window.get(s[j], 0) + 1
                if self.covers(window, need):
                    if j - i + 1 < best_len:
                        best_len, best_left = j - i + 1, i
                    break                       # longer ones can't be better
        return "" if best_len == float('inf') else s[best_left:best_left + best_len]

    def covers(self, window, need):
        for c in need:                          # at most 256 different chars
            if window.get(c, 0) < need[c]:      # not enough copies of c
                return False
        return True

7Code line by line

8Dry run (hand table)

s = "ADOBECODEBANC", t = "ABC".

Final answer: "BANC" ✓

9Complexity & remember

• O(n) to build tMap, then two nested loops O(m²), and each step calls the cover check over up to 256 characters → O(m² · 256), which is O(m²) since 256 is a constant. For m = 10⁵ → TLE, as she shows.
• Space O(256) for the two maps.

Part B · Sliding window: two maps + a "still needed" count

1The question again, with the new goal

Same question. Goal: O(m + n), with each pointer walking s once, and no cover-check loop on every step.

2What the constraints tell us now

• m up to 10⁵ → linear time.
• Maps hold at most 256 keys → O(1) space in big-O terms.

3Intuition: where is the repeated work?

From i = 1 the brute force found "DOBECODEBA" valid. When i moved to 2, it removed D and rebuilt everything from scratch. But D wasn't even needed! Without checking anything, we already know "OBECODEBA" is valid too. Then O is removed, also not needed, so "BECODEBA" is valid. Re-checking those is pure repetition.

So: keep one window. Right grows it until it covers t. Then left shrinks it as long as it still covers t, recording the size each time. When it stops covering, right grows again. It's sliding window and not two pointers because we care about the whole substring between the pointers, not just the two characters at the ends.

4Building the logic: the count, and why frequency matters

Getting rid of the cover check: a counter

Calling a match function after every step is slow. Instead, keep a number: count = how many characters of t are still missing. It starts at len(t) (3 for "ABC"). When count == 0, nothing is missing, so the window is valid. No loop needed.

First version of the rule, and where it breaks

First idea: when right brings in a character that's in t, do count −= 1. Walk it: A → 2, D (not in t), O (not in t), B → 1, E, C → 0. Valid: "ADOBEC". Record 6, then shrink: A leaves, and A is in t, so count += 1 → 1. Now left is at D.

Right continues: O, D, E (not in t), then B. B is in t, so the naive rule says count −= 1 → 0, "valid". But the window "DOBECODEB" has no A! What went wrong? The window already had a B (index 3). This second B is an extra copy; t asked for only one. It doesn't fill anything that was missing.

With this rule, the second B makes window[B] = 2 > need[B] = 1 → an extra copy → count stays 1. Correct. Then A arrives: window[A] = 1 ≤ 1 → count 0 → now valid ("DOBECODEBA").

Why do we shrink while the window is VALID?

This is the heart of the problem:

• When the window first becomes valid at some right, moving right further only makes longer windows. They're valid but useless for a minimum.
• The only way to find a shorter valid window ending at this right is to move left. Each step removes one character. If the window is still valid, it's a new, smaller candidate → record it, and keep going.
• The moment it becomes invalid (count > 0), we've lost a needed character. No smaller window ending here can be valid (it's missing that character too). So we stop shrinking and let right look for the missing character.

That's why the loop is while count == 0: (record, remove, move left), the opposite of the longest-window problems, where we shrink only while the window is broken.

Walking the shrink on the example

At right = 10 the window "DOBECODEBA" is valid. Shrink: D leaves (not needed) → "OBECODEBA" still valid. O leaves → still valid. B(3) leaves: window[B] was 2 > need 1, so it was an extra copy → count stays 0 → "ECODEBA" still valid. E leaves → "CODEBA" valid, length 6. C leaves: window[C] was 1 ≤ 1 → a required copy → count = 1 → stop. Right moves on: N, then C → count 0 → shrink O, D, E → "BANC" (4) → B leaves → count 1. Right reaches the end. Answer "BANC".

5Approach steps

1. need = Counter(t), window = {}, left = 0, count = len(t), best length = ∞.
2. For each right, c = s[right]: window[c] += 1; if c in need and window[c] ≤ need[c] → count −= 1.
3. While count == 0 (valid): record the window if shorter; d = s[left]; if d in need and window[d] ≤ need[d] → count += 1; window[d] −= 1; left += 1.
4. Return the best window, or "".

6Code (Python)

from collections import Counter

class Solution:
    def minWindow(self, s, t):
        need = Counter(t)                 # tMap
        window = {}                       # sMap: counts inside s[left..right]
        count = len(t)                    # characters of t still missing
        left = 0
        best_len, best_left = float('inf'), 0
        for right in range(len(s)):
            c = s[right]
            window[c] = window.get(c, 0) + 1          # right adds c
            if c in need and window[c] <= need[c]:   # a required copy arrived
                count -= 1
            while count == 0:                         # valid -> squeeze it
                if right - left + 1 < best_len:
                    best_len, best_left = right - left + 1, left
                d = s[left]
                if d in need and window[d] <= need[d]:   # losing a required copy
                    count += 1
                window[d] -= 1                        # left undoes right
                left += 1
        return "" if best_len == float('inf') else s[best_left:best_left + best_len]

7Code line by line

8Dry run (hand table)

s = "ADOBECODEBANC", t = "ABC". need = {A:1, B:1, C:1}, count starts at 3. "w" = the window map (only A, B, C shown; other letters are tracked too but never touch count).

Final answer: "BANC" ✓

9Complexity & remember

• O(n) to build need from t.
• right walks s once; it never comes back. left also only moves forward, at most m steps over the whole run. The while inside the for does not multiply. Total O(m + m) = O(2m), plus O(n) → O(m + n).
• Space: two maps, each at most 256 keys. Twice the space of Part D.

Part C · The same window with a formed / required counter

Not from the video. It's the other common way to write Part B's counter, and you'll meet it in editorials. Same window, same shrinking. Only the meaning of the counter changes.

1The idea in simple words

Instead of counting copies still missing, count distinct characters that are fully satisfied:

• required = how many different characters t has. For t = "AABC" that's 3 (A, B, C), not 4.
• formed = how many of those characters currently have enough copies in the window (window[c] ≥ need[c]).
• The window is valid exactly when formed == required.

2When does formed change? Only at the crossing moment

Think of each character of t as a small progress bar that fills up to need[c]:

• Right adds c, and window[c] becomes exactly need[c] → the bar just filled → formed += 1.
• Left removes c, and window[c] drops to exactly need[c] − 1 → the bar just stopped being full → formed −= 1.

3Why we shrink while valid (the same reason, said once more)

While formed == required, the window covers t. Moving right would only make it longer, so the only way to find something shorter is to drop characters from the left, recording each valid size. As soon as a needed character falls below its count (formed < required), every smaller window ending at this right is missing it too, so we stop and expand right again. Because coverage is monotonic, left never has to go back.

4Code (Python)

from collections import Counter

class Solution:
    def minWindow(self, s, t):
        need = Counter(t)
        required = len(need)              # distinct characters t needs
        window = {}
        formed = 0                        # distinct characters fully satisfied
        left = 0
        best_len, best_left = float('inf'), 0
        for right in range(len(s)):
            c = s[right]
            window[c] = window.get(c, 0) + 1
            if c in need and window[c] == need[c]:   # c just became satisfied
                formed += 1
            while formed == required:                # valid -> squeeze it
                if right - left + 1 < best_len:
                    best_len, best_left = right - left + 1, left
                d = s[left]
                window[d] -= 1
                if d in need and window[d] == need[d] - 1:   # d just fell short
                    formed -= 1
                left += 1
        return "" if best_len == float('inf') else s[best_left:best_left + best_len]

5Dry run with duplicates in t (hand table)

s = "AABXAB", t = "AAB" → need = {A:2, B:1}, required = 2. Here count-of-copies and formed differ visibly.

Answer "AAB" ✓. Step 6 shows an extra B that changes nothing, because B was already satisfied.

6Complexity & remember

Same as Part B: O(m + n) time, two maps of at most 256 keys.

Part D · Space-optimised: one map with negative counts

1What's the same and what changes

The window, the count (starts at len(t), valid at 0), and "shrink while valid" are all the same as Part B. The change: no separate window map. We keep only need, and let it go up and down.

The teacher's view: beginners naturally think of two maps first (that's why she taught Part B), and almost nobody comes up with the one-map version straight away. So learn it as a step after Part B.

2Intuition: need[c] = "how many more c's do I still want?"

• Start: need = counts of t. e.g. {A:1, B:1, C:1}.
• Right takes c: need[c] −= 1 for every character, even ones not in t. Before decreasing, if need[c] was > 0, this copy was really wanted → count −= 1.
• So need[c] can go negative. For a character not in t, D → −1 means "one D in the window that nobody asked for". For B → −1, it means "one spare B".
• Left gives c back: need[c] += 1. If after adding it's > 0, we just lost a wanted copy → count += 1.

In short: positive = still wanted, 0 = exactly satisfied, negative = spare copies. One number per character does the job of two maps.

3Approach steps

1. need = Counter(t), count = len(t), left = 0, best length = ∞.
2. For each right, c = s[right]: if need[c] > 0 → count −= 1. Then need[c] −= 1.
3. While count == 0: record if shorter; d = s[left]; need[d] += 1; if need[d] > 0 → count += 1; left += 1.
4. Return the best window or "".

4Code (Python)

from collections import Counter

class Solution:
    def minWindow(self, s, t):
        need = Counter(t)                 # how many more of each char we want
        count = len(t)                    # wanted copies still missing
        left = 0
        best_len, best_left = float('inf'), 0
        for right in range(len(s)):
            c = s[right]
            if need[c] > 0:               # this copy fills a real gap
                count -= 1
            need[c] -= 1                  # right always takes one (may go negative)
            while count == 0:             # valid -> squeeze it
                if right - left + 1 < best_len:
                    best_len, best_left = right - left + 1, left
                d = s[left]
                need[d] += 1              # left gives it back
                if need[d] > 0:           # now we're short of d again
                    count += 1
                left += 1
        return "" if best_len == float('inf') else s[best_left:best_left + best_len]

5Code line by line

6Dry run (hand table)

s = "ADOBECODEBANC", t = "ABC". The map column shows need for A, B, C and the extra letters (D, O, E, N).

Same steps and the same answer, "BANC" ✓, with one map. Look at step 10: B goes to −1, which says "one spare B", the same thing Part B tracked as window[B] = 2 > need 1.

7Complexity & remember

• Time O(m + n), the same as Part B (both pointers move forward only).
• Space: one map instead of two, half the memory. The time complexity doesn't change; only the space does.

Part E · Revision page

s = Solution()
print(repr(s.minWindow("ADOBECODEBANC", "ABC")))   # 'BANC'
print(repr(s.minWindow("a", "a")))                 # 'a'
print(repr(s.minWindow("a", "aa")))                # ''
print(repr(s.minWindow("AABXAB", "AAB")))          # 'AAB'
print(repr(s.minWindow("ab", "b")))                # 'b'
print(repr(s.minWindow("abc", "cba")))             # 'abc'

Based on this video: Minimum Window Substring | Brute Force, Two Maps & One Map