My no-repeat finder says 2, but “vdf” has 3

DSA · Core
25 min read, about 1 h 30 min with practice

Concept
Asked often: high
Reviewed 2026-11

New to some of the words above? Open a quick recap. Each takes about two minutes.

Quick recapBig-O in two minutes· 2 min

Big-O says how the work grows as the input grows. One loop over n items is O(n): twice the items, twice the work. A loop inside a loop is O(n²): twice the items, four times the work. Space is the same idea for the extra memory: a few numbers is O(1), a copy of the input is O(n). The full lesson: My code passed every test, then timed out on the big one.

Quick recapSets and Counter in two minutes· 2 min

A set answers “is it in here?” in about one step: c in seen, seen.add(c) and seen.remove(c) are each O(1). A Counter from collections is a dict of counts: need = Counter("aab") gives {'a': 2, 'b': 1}, and a missing key counts as 0, so need[c] -= 1 works for any c. The full lesson: My anagram check says aab and abb match.

Quick recapTwo pointers in two minutes· 2 min

Two indexes into one list, often lo and hi. Each step looks at them and moves one, so n items take about n steps. They can walk in from both ends, or both go the same way: a slow one and a fast one. Each move must be safe: say why nothing is missed before you code it. The full lesson: My tank finder says 40, but two walls hold 49.

See the problem

The interview task: find the longest stretch of a string with no character in it twice. You keep a set of the stretch so far, and when a character repeats, you start again from it:

def longest_unique(s):
    best = run = 0
    seen = set()
    for c in s:
        if c in seen:  # a repeat: start again from here
            seen = set()
            run = 0
        seen.add(c)
        run += 1
        best = max(best, run)
    return best

For "dvdf", it reads d and v, then d again, and starts over at the second d: “d”, then “df”. It says 2. But “vdf” has no repeat, and it’s 3.

Starting over threw away the v. The v was fine: only the first d had to go.

Define the task

Write longest_unique(s).

Input: s, up to 200,000 characters of any kind: letters, digits, spaces, emoji, any language. A and a are different characters.
Output: the length of the longest stretch of s, characters in a row, with no character in it twice. For an empty s, 0.
The hard part: 200,000 characters make about 20 billion stretches. It must be fast anyway.

Example: longest_unique("abcabcbb") is 3, for “abc”. longest_unique("dvdf") is 3, for “vdf”.

Pause and think

Hints open one at a time:

Hint 1 of 3

Only the first d clashes with the new one. Everything after it, here the v, can stay.

Hint 2 of 3

So keep a window: a stretch with no repeats, from lo to hi. Each new character joins at the right. When it’s in the window already, drop characters from the left until the old copy is gone.

Hint 3 of 3

Keep the window’s characters in a set, so “is it in the window?” is one step. Each character joins once and leaves at most once: about 2n steps, not n²/2.

Understand the idea

A window is a stretch from lo to hi. It’s two pointers that both walk right. hi reads the next character, and lo marks where the window starts. The window is s[lo:hi + 1].

Grow at the right, shrink at the left. Each new character joins at the right. If the window would then hold it twice, drop characters from the left until it wouldn’t. Now the window is the longest stretch with no repeats that ends at hi. Check its length, and move on.

lo never moves back. Say the window from lo holds a repeat. Then every stretch that starts before lo and reaches hi holds that repeat too. So lo only moves right, and each character joins once and leaves at most once: at most 2n steps.

A set says what’s in the window. c in seen takes about one step, as in the hashing lesson, so each join and each drop is O(1).

Two kinds of window. Some have a fixed size k: each step adds one item and drops one, as for the biggest sum of k in a row, the first practice problem. Others grow and shrink, as here: they grow while the window is fine, and shrink when it breaks the rule.

Shrinking is safe when smaller windows keep the rule. Every stretch inside a stretch with no repeats has no repeats either. So once a window is fine again, there’s no need to drop more. A rule like “adds up to at least 7” works the same way, as long as every number is above 0: that’s the second practice problem.

Watch it. The faded characters have left the window. Try your own, like abcabcbb, or bbbbb.

A window that grows and shrinks

Work so far

window	''
longest so far	0

Step 1 of 15. The window starts empty, at lo = 0. hi reads the characters one by one, and each joins the window.

Speed Ask me first Show as text

1def longest_unique(s: str) -> int:
2    seen = set()  # the characters in s[lo:hi + 1]
3    best = lo = 0
4    for hi, c in enumerate(s):
5        while c in seen:  # a repeat: drop from the left
6            seen.remove(s[lo])
7            lo += 1
8        seen.add(c)
9        best = max(best, hi - lo + 1)
10    return best

Climb the ladder

All three give 3 for "dvdf". What changes is how many characters they read.

The idea: For each start i, add characters to a set until one repeats. That’s the longest stretch from i. Keep the longest of all.

It checks every start, so it can’t miss the best one.

def longest_unique(s: str) -> int:
    best = 0
    for i in range(len(s)):  # every start
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break  # a repeat: the stretch from i ends here
            seen.add(s[j])
        best = max(best, len(seen))
    return best

Time: O(n²)
Space: O(k)
Why: From each start, it reads until a repeat: up to n characters, for each of n starts. The set holds up to k characters, the number of different ones.

Where it breaks: 200,000 different characters, so no stretch ever hits a repeat. Every start reads to the end: about 20 billion reads. It runs out of time on the first speed test.

The idea: Read from a start until a character repeats. Then start again just past its earlier copy, with an empty set: any start before that hits the same repeat, and stops sooner.

The waste in Okay: it tries starts that can’t win. A start before the earlier copy holds both copies by the time it reaches the repeat.

Highlighted lines are new in this rung.

def longest_unique(s: str) -> int:
    best = 0
    start = 0
    while start < len(s):
        seen = set()
        j = start
        while j < len(s) and s[j] not in seen:
            seen.add(s[j])
            j += 1
        best = max(best, j - start)
        if j == len(s):
            break  # it reached the end, so no later start does better
        start = s.index(s[j], start) + 1  # start again just past the earlier copy
    return best

Time: O(n²) at worstwas O(n²)
Space: O(k)
Why: When characters rarely repeat, it reads each one about once. But each start reads its whole stretch again, so when the same m characters come again and again, every start reads m of them: about n × m.

What changed from the previous rung

def longest_unique(s: str) -> int:
    best = 0
    for i in range(len(s)):  # every start
    start = 0
    while start < len(s):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break  # a repeat: the stretch from i ends here
        j = start
        while j < len(s) and s[j] not in seen:
            seen.add(s[j])
        best = max(best, len(seen))
            j += 1
        best = max(best, j - start)
        if j == len(s):
            break  # it reached the end, so no later start does better
        start = s.index(s[j], start) + 1  # start again just past the earlier copy
    return best

Where it breaks: 200,000 characters, the same 2,000 again and again. Each start reads 2,000 characters before it hits a repeat: about 400 million reads. It runs out of time on the second speed test, though 200,000 different characters are quick.

The idea: Keep a window from lo to hi, and a set of its characters. Each new character joins at the right. If it’s in the set already, drop characters from the left until it isn’t.

The waste in Better: each new start reads its stretch again from scratch, though all of it after the earlier copy was still fine. The window keeps that part, and drops only what has to go.

Highlighted lines are new in this rung.

def longest_unique(s: str) -> int:
    seen = set()  # the characters in s[lo:hi + 1]
    best = lo = 0
    for hi, c in enumerate(s):
        while c in seen:  # a repeat: drop from the left
            seen.remove(s[lo])
            lo += 1
        seen.add(c)
        best = max(best, hi - lo + 1)
    return best

Time: O(n)was O(n²) at worst
Space: O(k)
Why: hi reads each character once, and lo drops each one at most once: at most 2n steps.

What changed from the previous rung

def longest_unique(s: str) -> int:
    best = 0
    start = 0
    while start < len(s):
        seen = set()
        j = start
        while j < len(s) and s[j] not in seen:
            seen.add(s[j])
            j += 1
        best = max(best, j - start)
        if j == len(s):
            break  # it reached the end, so no later start does better
        start = s.index(s[j], start) + 1  # start again just past the earlier copy
    seen = set()  # the characters in s[lo:hi + 1]
    best = lo = 0
    for hi, c in enumerate(s):
        while c in seen:  # a repeat: drop from the left
            seen.remove(s[lo])
            lo += 1
        seen.add(c)
        best = max(best, hi - lo + 1)
    return best

When Best isn’t best: when a smaller window can break the rule that a bigger one keeps. For “the shortest stretch that adds up to at least 7”, with numbers below 0, dropping a number can make the sum go up. Then shrinking isn’t safe, and a sliding window can miss the answer. Running totals, from the prefix sums topic, fit there.

Write it yourself

Now write it in the page. Press Run tests to check your code. Python runs in your browser, so nothing is sent anywhere. Your code is saved in this browser for next time.

Try Okay from the ladder first: it runs out of time on 200,000 different characters. Better passes that one, but runs out of time when the same 2,000 come again and again.

The longest stretch with no repeats

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: longest_unique('abcabcbb') → 3
Not run yet: longest_unique("dvdf"): starting over at the second d misses "vdf" → 3
Not run yet: longest_unique('bbbbb') → 1
Not run yet: longest_unique('pwwkew') → 3
Not run yet: longest_unique("abba"): the second a’s earlier copy has already left the window → 2
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 200,000 different characters → 200000
Not run yet: Speed test: 200,000 characters, the same 2,000 again and again → 2000

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: every start	O(n²)	O(k)	Checks every start, so it’s easy to trust	Reads the same characters again from every start	A few characters, checked by hand
Better: start again past the copy	O(n²) at worst	O(k)	Skips starts that can’t win	The same few thousand characters again and again defeat it	Hardly ever: Best is as short
Best: sliding window	O(n)	O(k)	At most 2n steps, whatever the string	Needs the reason `lo` never moves back	Always, for this problem

Here k is the number of different characters: at most 26 for lower-case letters, but up to n for any characters.

How much work is that? Each bar is one rung, for n characters made of the same n/100 again and again: 2,000 for 200,000. Pick a size, or run the race.

Reading n characters, the same n/100 again and again

OkayEvery start · O(n²)≈ 400,000,000 characters read
BetterStart again past the copy · O(n²) at worst≈ 400,000,000 characters read
BestA sliding window · O(n)≈ 400,000 characters read

At n = 200,000, Okay does about 1,000 times more work than Best.

Every bar does the same number of steps per second, so the race shows which rung finishes first. Turn on Log scale to compare the short bars.

Here Okay and Better read about the same: every start reads n/100 characters before it hits a repeat. Better’s skip only helps when repeats are far apart. Best reads each character at most twice, once as it joins and once as it leaves.

Every step here is a step of Python, so the race is close to the real times. In this page’s Python, 10,000 different characters take Okay about 10 to 25 seconds, depending on the computer. Twice as many take about 4 times as long. On 20,000 characters made of the same 2,000, Better takes 5 seconds or more, and twice as many take about twice as long. Best takes under a fifth of a second for 200,000 characters.

Common mistakes and edge cases

The length is hi - lo + 1. Both ends are in the window: from 1 to 3 is 3 characters.
Shrink with while, not if. The earlier copy can be several characters in. For “vdfx” and a new f, three characters leave.
lo never moves back. If you jump lo with a dict of where each character was last seen, use lo = max(lo, last[c] + 1). For "abba", the second a was last seen at 0, which has already left the window: without max, lo jumps back and the answer is 3, not 2.
An empty string. The loop never runs, and it returns 0. Test it anyway.
Shrinking needs a rule that smaller windows keep. No repeats, or a sum of numbers above 0 that’s still big enough. With numbers below 0, it doesn’t hold.

Say it in the interview

Questions to ask first

What counts as a character: letters only, or anything? Are A and a different?
Do you want the length, or the stretch itself?
How long can the string be?

A 60-second walkthrough

“I’ll keep a window from lo to hi with no repeats, and a set of its characters. For each new character at hi, if it’s in the set already, I drop characters from the left until it isn’t. Then I add it and check the length, hi minus lo plus one. lo never moves back: any stretch that starts earlier and reaches hi holds the same repeat. So each character joins once and leaves at most once: O(n) time, and O(k) memory for the set, where k is the number of different characters.”

Likely follow-ups

Return the stretch, not its length? Keep lo when the best changes, and slice once at the end.
Can lo jump instead of stepping? Yes: keep a dict of where each character was last seen, and set lo = max(lo, last[c] + 1). Still O(n), with fewer steps.
At most 2 different characters, not none twice? The same window, with a dict of counts: shrink while it holds more than 2 kinds.
Why not start over at a repeat? It throws away the characters after the earlier copy: 2 for “dvdf”, when “vdf” is 3.

Practice

Three problems, from easy to hard: the biggest sum of k in a row, the fewest days to reach a goal, and the shortest stretch that holds a word. Each has hints, tests you can run here, and its own Okay, Better and Best answers. For each rung, say its Big-O before you open it.

1. The biggest sum of k in a row (easy)

Write biggest_sum(nums, k). nums holds a shop’s takings for each day, and a day with refunds is below 0. Return the biggest total of k days in a row. k is at least 1, and at most len(nums).

Example: biggest_sum([2, 1, 5, 1, 3, 2], 3) is 9: 5 + 1 + 3.

Hint 1 of 3

Adding up each window again reads k numbers for every window. Two windows side by side share k − 1 of them.

Hint 2 of 3

Slide the window one step: add the number coming in, and take away the one going out.

Hint 3 of 3

Add up the first k. Then for each i from k on, add nums[i] and take away nums[i − k]. Keep the biggest.

The biggest sum of k in a row

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: biggest_sum([2, 1, 5, 1, 3, 2], 3) → 9
Not run yet: biggest_sum([1, 9, 1, 1, 1, 8, 8], 2): the biggest number isn’t in the best window → 16
Not run yet: biggest_sum([-3, -1, -2], 2): every window is below 0 → -3
Not run yet: biggest_sum([4, -1, 2], 3) → 5
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 200,000 numbers, k = 100,000 → 49950000
Not run yet: 200,000 numbers, k = 10, in 1 MB → 995

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Show the Okay, Better and Best answers

The idea: For each start i, add up nums[i:i + k] with sum(), and keep the biggest.

It adds up each window, word for word, so it’s easy to trust.

def biggest_sum(nums: list[int], k: int) -> int:
    best = sum(nums[:k])
    for i in range(1, len(nums) - k + 1):
        best = max(best, sum(nums[i : i + k]))  # add up each window again
    return best

Time: O(n × k)
Space: O(k)
Why: n − k + 1 windows, and each sum reads k numbers, from a slice it copies first.

Where it breaks: 200,000 numbers with k = 100,000: about 10 billion numbers read. It runs out of time on the speed test.

The idea: Make a list of running totals: totals[i] is the sum of the first i numbers. Then the window from i adds up to totals[i + k] − totals[i], in one step.

The waste in Okay: it adds up the same numbers again for every window.

Highlighted lines are new in this rung.

def biggest_sum(nums: list[int], k: int) -> int:
    totals = [0]  # totals[i] is the sum of the first i numbers
    for x in nums:
        totals.append(totals[-1] + x)
    return max(totals[i + k] - totals[i] for i in range(len(nums) - k + 1))

Time: O(n)was O(n × k)
Space: O(n)was O(k)
Why: One pass to build the totals, and one to try each window.

What changed from the previous rung

def biggest_sum(nums: list[int], k: int) -> int:
    best = sum(nums[:k])
    for i in range(1, len(nums) - k + 1):
        best = max(best, sum(nums[i : i + k]))  # add up each window again
    return best
    totals = [0]  # totals[i] is the sum of the first i numbers
    for x in nums:
        totals.append(totals[-1] + x)
    return max(totals[i + k] - totals[i] for i in range(len(nums) - k + 1))

Where it breaks: it passes the speed test, but its list of totals is as long as the input. 200,000 numbers take more than 1 MB, so it fails the memory test.

The idea: Add up the first k. Then step right: add the number coming in, and take away the one going out. Keep the biggest.

The waste in Better: it keeps a total for every day, when each step only needs the window’s own sum.

Highlighted lines are new in this rung.

def biggest_sum(nums: list[int], k: int) -> int:
    window = 0
    for i in range(k):  # add up the first k
        window += nums[i]
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]  # add the new one, take away the oldest
        best = max(best, window)
    return best

Time: O(n)
Space: O(1)was O(n)
Why: One pass, and two numbers: the window’s sum and the best.

What changed from the previous rung

def biggest_sum(nums: list[int], k: int) -> int:
    totals = [0]  # totals[i] is the sum of the first i numbers
    for x in nums:
        totals.append(totals[-1] + x)
    return max(totals[i + k] - totals[i] for i in range(len(nums) - k + 1))
    window = 0
    for i in range(k):  # add up the first k
        window += nums[i]
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]  # add the new one, take away the oldest
        best = max(best, window)
    return best

When Best isn’t best: when you need many windows of different sizes, or any range someone asks for. Then the running totals of Better answer each one in a step.

2. The fewest days to reach a goal (medium)

Write shortest_run(nums, target). nums holds the steps you walked each day, each 1 or more. Return the fewest days in a row whose steps add up to at least target, or 0 if no run does. target is at least 1.

Example: shortest_run([2, 3, 1, 2, 4, 3], 7) is 2: 4 + 3.

Hint 1 of 3

Every day is 1 or more, so a longer run adds up to more. Once a window reaches the goal, any window around it does too.

Hint 2 of 3

Grow the window at the right until it reaches the goal. Then shrink it from the left while it still does, and keep the shortest.

Hint 3 of 3

Keep the window’s sum as you go: add each day as it joins at hi, and take it away as it leaves at lo. Each day joins once and leaves at most once.

The fewest days to reach a goal

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: shortest_run([2, 3, 1, 2, 4, 3], 7) → 2
Not run yet: shortest_run([1, 4, 4], 4) → 1
Not run yet: shortest_run([1, 1, 1, 1, 1], 11): no run reaches it → 0
Not run yet: shortest_run([1, 2, 3, 4, 5], 15): only the whole list → 5
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 200,000 days of 1 step, and only all of them reach the goal → 200000
Not run yet: 200,000 days, in 1 MB → 91

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Show the Okay, Better and Best answers

The idea: For each start, add days until the sum reaches the goal, and keep the shortest.

It tries every start, so it can’t miss the shortest run.

def shortest_run(nums: list[int], target: int) -> int:
    best = 0
    for i in range(len(nums)):  # every start
        total, j = 0, i  # grow nums[i:j] until it reaches the target
        while j < len(nums) and total < target:
            total += nums[j]
            j += 1
        if total >= target and (best == 0 or j - i < best):
            best = j - i
    return best

Time: O(n²)
Space: O(1)
Why: Each start can read every day after it.

Where it breaks: 200,000 days of 1 step, with a goal of 200,000. Only the whole list reaches it, so every start reads to the end: about 20 billion steps. It runs out of time.

The idea: Make running totals. They only grow, since every day is 1 or more, so for each start, bisect finds the first end that reaches the goal.

The waste in Okay: each start adds up the same days again.

Highlighted lines are new in this rung.

from bisect import bisect_left


def shortest_run(nums: list[int], target: int) -> int:
    totals = [0]  # totals[i] is the sum of the first i numbers
    for x in nums:
        totals.append(totals[-1] + x)
    best = 0
    for i in range(len(nums)):
        # The first end j where totals[j] - totals[i] reaches target. Totals only grow.
        j = bisect_left(totals, totals[i] + target)
        if j <= len(nums) and (best == 0 or j - i < best):
            best = j - i
    return best

Time: O(n log n)was O(n²)
Space: O(n)was O(1)
Why: One pass to build the totals, then a bisect of about log n steps for each start.

What changed from the previous rung

from bisect import bisect_left


def shortest_run(nums: list[int], target: int) -> int:
    totals = [0]  # totals[i] is the sum of the first i numbers
    for x in nums:
        totals.append(totals[-1] + x)
    best = 0
    for i in range(len(nums)):  # every start
        total, j = 0, i  # grow nums[i:j] until it reaches the target
        while j < len(nums) and total < target:
            total += nums[j]
            j += 1
        if total >= target and (best == 0 or j - i < best):
    for i in range(len(nums)):
        # The first end j where totals[j] - totals[i] reaches target. Totals only grow.
        j = bisect_left(totals, totals[i] + target)
        if j <= len(nums) and (best == 0 or j - i < best):
            best = j - i
    return best

Where it breaks: it’s quick, but its list of totals is as long as the input. 200,000 days take more than 1 MB, so it fails the memory test.

The idea: Grow the window at the right. Whenever its sum reaches the goal, note its length, and shrink it from the left while it still does.

The waste in Better: it keeps every running total and searches them, when the window only needs its own sum.

Highlighted lines are new in this rung.

def shortest_run(nums: list[int], target: int) -> int:
    best = 0
    total = lo = 0  # the sum of the window, nums[lo:hi + 1]
    for hi, x in enumerate(nums):
        total += x
        while total >= target:  # shrink from the left while it still reaches
            if best == 0 or hi - lo + 1 < best:
                best = hi - lo + 1
            total -= nums[lo]
            lo += 1
    return best

Time: O(n)was O(n log n)
Space: O(1)was O(n)
Why: Each day joins once and leaves at most once, and it keeps just the window’s sum.

What changed from the previous rung

from bisect import bisect_left


def shortest_run(nums: list[int], target: int) -> int:
    totals = [0]  # totals[i] is the sum of the first i numbers
    for x in nums:
        totals.append(totals[-1] + x)
    best = 0
    for i in range(len(nums)):
        # The first end j where totals[j] - totals[i] reaches target. Totals only grow.
        j = bisect_left(totals, totals[i] + target)
        if j <= len(nums) and (best == 0 or j - i < best):
            best = j - i
    total = lo = 0  # the sum of the window, nums[lo:hi + 1]
    for hi, x in enumerate(nums):
        total += x
        while total >= target:  # shrink from the left while it still reaches
            if best == 0 or hi - lo + 1 < best:
                best = hi - lo + 1
            total -= nums[lo]
            lo += 1
    return best

When Best isn’t best: when days can be 0 or below. Then a longer run can add up to less, so shrinking isn’t safe. Running totals with a queue of the smallest ones so far fit there.

3. The shortest stretch that holds a word (hard)

Write shortest_cover(text, word). Return the shortest stretch of text, characters in a row, that holds every character of word, as many times as word has it. If more than one is the shortest, return the first. If none holds it, return "". word has at least 1 character, and A and a are different.

Example: shortest_cover("ADOBECODEBANC", "ABC") is "BANC".

Hint 1 of 3

Grow a window until it holds the whole word. Then shrink it from the left while it still does: that’s the shortest one that ends there.

Hint 2 of 3

Keep a Counter of what the window still needs. Each character that joins takes 1 off its count, and each that leaves puts 1 back.

Hint 3 of 3

Checking every character of the word at every step is slow when the word is long. Keep one more number: how many characters the window still lacks. When it’s 0, the window holds the word.

The shortest stretch that holds a word

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: shortest_cover('ADOBECODEBANC', 'ABC') → 'BANC'
Not run yet: shortest_cover("a", "aa"): repeats count → ''
Not run yet: shortest_cover('aa', 'aa') → 'aa'
Not run yet: shortest_cover("xyzyx", "xy"): two of the same size, so the first → 'xy'
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 99,999 a’s, then a b → 'ab'
Not run yet: Speed test: 200,000 characters, and a word of 2,000 different ones

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Show the Okay, Better and Best answers

The idea: For each start, grow a Counter of the stretch until it holds the word, checking every character of the word at each step.

It tries every start, so it can’t miss the shortest stretch.

from collections import Counter


def shortest_cover(text: str, word: str) -> str:
    need = Counter(word)
    best_lo, best_len = 0, 0
    for lo in range(len(text)):  # every start
        have = Counter()
        hi = lo  # grow text[lo:hi] until it holds the whole word
        while hi < len(text) and any(have[c] < k for c, k in need.items()):
            have[text[hi]] += 1
            hi += 1
        holds = all(have[c] >= k for c, k in need.items())
        if holds and (best_len == 0 or hi - lo < best_len):
            best_lo, best_len = lo, hi - lo
    return text[best_lo : best_lo + best_len]

Time: O(n² × m)
Space: O(k)
Why: Each start can read to the end, and each step checks the m different characters of the word. The Counter holds up to k, the different characters of the text.

Where it breaks: 99,999 a’s, then a b. Every start reads to the b: about 5 billion steps. It runs out of time on the first speed test.

The idea: Keep one window. Grow it at the right, and while it holds the word, note it and shrink it from the left. To check, compare every character of the word.

The waste in Okay: it starts again from every start, though most of the last window is still good.

Highlighted lines are new in this rung.

from collections import Counter


def shortest_cover(text: str, word: str) -> str:
    need = Counter(word)
    have = Counter()  # the characters in the window, text[lo:hi + 1]
    best_lo, best_len = 0, 0
    lo = 0
    for hi, c in enumerate(text):
        have[c] += 1
        while all(have[ch] >= k for ch, k in need.items()):  # it holds the whole word
            if best_len == 0 or hi - lo + 1 < best_len:
                best_lo, best_len = lo, hi - lo + 1
            have[text[lo]] -= 1  # shrink from the left
            lo += 1
    return text[best_lo : best_lo + best_len]

Time: O(n × m)was O(n² × m)
Space: O(k)
Why: Each character joins once and leaves at most once, but every step checks up to m counts.

What changed from the previous rung

from collections import Counter


def shortest_cover(text: str, word: str) -> str:
    need = Counter(word)
    have = Counter()  # the characters in the window, text[lo:hi + 1]
    best_lo, best_len = 0, 0
    for lo in range(len(text)):  # every start
        have = Counter()
        hi = lo  # grow text[lo:hi] until it holds the whole word
        while hi < len(text) and any(have[c] < k for c, k in need.items()):
            have[text[hi]] += 1
            hi += 1
        holds = all(have[c] >= k for c, k in need.items())
        if holds and (best_len == 0 or hi - lo < best_len):
            best_lo, best_len = lo, hi - lo
    lo = 0
    for hi, c in enumerate(text):
        have[c] += 1
        while all(have[ch] >= k for ch, k in need.items()):  # it holds the whole word
            if best_len == 0 or hi - lo + 1 < best_len:
                best_lo, best_len = lo, hi - lo + 1
            have[text[lo]] -= 1  # shrink from the left
            lo += 1
    return text[best_lo : best_lo + best_len]

Where it breaks: a word of 2,000 different characters, in 200,000 characters. Every step checks up to 2,000 counts: about 600 million checks. It runs out of time on the second speed test.

The idea: Keep need, a Counter of how many more of each character the window needs, and missing, how many it lacks in all. A character that joins takes 1 off its need, and off missing if it was still needed. When missing is 0, the window holds the word.

The waste in Better: it checks every character of the word at every step, though only one count changed.

Highlighted lines are new in this rung.

from collections import Counter


def shortest_cover(text: str, word: str) -> str:
    need = Counter(word)  # how many more of each the window needs (below 0: spares)
    missing = len(word)  # characters of word the window still lacks, repeats counted
    best_lo, best_len = 0, 0
    lo = 0
    for hi, c in enumerate(text):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1
        while missing == 0:  # it holds the whole word
            if best_len == 0 or hi - lo + 1 < best_len:
                best_lo, best_len = lo, hi - lo + 1
            need[text[lo]] += 1  # shrink from the left
            if need[text[lo]] > 0:
                missing += 1
            lo += 1
    return text[best_lo : best_lo + best_len]

Time: O(n + m)was O(n × m)
Space: O(k)
Why: Each character joins once and leaves at most once, and each takes a step or two. Counting the word takes m more.

What changed from the previous rung

from collections import Counter


def shortest_cover(text: str, word: str) -> str:
    need = Counter(word)
    have = Counter()  # the characters in the window, text[lo:hi + 1]
    need = Counter(word)  # how many more of each the window needs (below 0: spares)
    missing = len(word)  # characters of word the window still lacks, repeats counted
    best_lo, best_len = 0, 0
    lo = 0
    for hi, c in enumerate(text):
        have[c] += 1
        while all(have[ch] >= k for ch, k in need.items()):  # it holds the whole word
        if need[c] > 0:
            missing -= 1
        need[c] -= 1
        while missing == 0:  # it holds the whole word
            if best_len == 0 or hi - lo + 1 < best_len:
                best_lo, best_len = lo, hi - lo + 1
            have[text[lo]] -= 1  # shrink from the left
            need[text[lo]] += 1  # shrink from the left
            if need[text[lo]] > 0:
                missing += 1
            lo += 1
    return text[best_lo : best_lo + best_len]

When Best isn’t best: when the order matters too. The shortest stretch that holds the word’s characters in order, with others between, needs a different scan: from each match of the word’s first character, forward, then back.

Check yourself

A few quick questions. Ones you miss are remembered, so you can find your weak spots later.

Predict the outputWhat does this print?

s = "abcab"
seen, lo = set(), 0
for c in s:
    while c in seen:
        seen.remove(s[lo])
        lo += 1
    seen.add(c)
print(lo)

0123

Multiple choiceThe window is "vdfx", and the next character is f. How many characters leave before f joins?
1234
Spot the bugThis should return the length of the longest stretch with no character twice. What's wrong?
```
def longest_unique(s):
    last = {}
    best = lo = 0
    for hi, c in enumerate(s):
        if c in last:
            lo = last[c] + 1
        last[c] = hi
        best = max(best, hi - lo + 1)
    return best
```
lo can jump back to a place the window has already passedThe length should be hi − lolast should be a setNothing
Multiple choiceIn the longest stretch with no repeats, why does lo never need to move back to the left?
Any stretch that starts before lo and reaches hi holds the same repeatThe characters before lo are all the sameMoving back would be slower, but give the same answerIt does, when the next character is new
Pick the patternYou have each day’s takings, and some days are below 0 because of refunds. Find the biggest total of 7 days in a row, with O(1) extra memory.
A window of fixed size: add the day coming in, take away the day going outA window that grows while the sum is above 0, and starts again when it isn'tSort the days, and add up the 7 biggestAdd up every 7 days in a row again

Flashcards

Add these to your review deck. Each card comes back a little later every time you get it right.

Cheat sheet

A window is s[lo:hi + 1]: two pointers, both walking right. Its length is hi - lo + 1.
Grow at the right with for hi, c in enumerate(s). Shrink at the left with while the window breaks the rule.
Each item joins once and leaves at most once: O(n), with a set or a Counter for what’s inside.
A fixed-size window: add the one coming in, take away the one going out.
Shrinking is safe only when smaller windows keep the rule: no repeats, or a sum of numbers above 0.
No repeats: drop up to the earlier copy, not the whole window.
A word’s characters: keep need and one missing count, so each step is O(1).

Go deeper

Step through more: No repeats on the DSA visualizer, and the biggest sum of k in a row.
The two pointers lesson walks in from both ends instead.
The hashing lesson shows why c in seen is about one step.
Next on the DSA roadmap: binary search.

Can you do these now?

If you’re not sure of any of these, scroll back to that part before moving on.

Grow a window at the right and shrink it at the left, and say why each item joins and leaves at most once
Find the longest stretch with no character twice in O(n)
Tell a window of fixed size from one that grows and shrinks, and say when shrinking is safe
Use a sliding window to find the biggest sum of k in a row, or the shortest run that meets a goal

Status: Not started

My no-repeat finder says 2, but “vdf” has 3

See the problem

Define the task

Pause and think

Understand the idea

Climb the ladder

Every start

Start again past the earlier copy

A sliding window

Write it yourself

The longest stretch with no repeats

Compare

Common mistakes and edge cases

Say it in the interview

Practice

1. The biggest sum of k in a row (easy)

The biggest sum of k in a row

Add up every window

Running totals

Slide the window

2. The fewest days to reach a goal (medium)

The fewest days to reach a goal

Every start

Running totals and bisect

Grow and shrink

3. The shortest stretch that holds a word (hard)

The shortest stretch that holds a word

Every start

Grow and shrink, checking the whole word

Count what’s missing

Check yourself

Flashcards

Cheat sheet

Go deeper

Can you do these now?