Longest Substring Without Repeats

Don't reread what you already proved clean

A door log holds 100,000 badge swipes in time order. Security wants the longest run of consecutive swipes in which no badge appears twice.

The obvious plan starts a walk at every swipe and reads forward until some badge repeats. If the log has long repeat-free stretches, each walk runs a long way. In the worst case no badge repeats at all, and the walks read 100,000 + 99,999 + … + 1 = 5,000,050,000 swipes.

Look at what the walks repeat. Walk 0 stops at the first repeat. Walk 1 then rereads almost everything walk 0 just read, a stretch walk 0 has already proved repeat-free. The fast version keeps that proof. When a repeat arrives, it drops swipes from the front only until the older copy is gone, keeps the rest, and carries on reading. Every swipe enters the stretch once and leaves at most once, so the whole job takes at most 200,000 set updates instead of five billion reads.

That is the big idea of this lesson: a stretch with no repeats still has none after you trim its front, so you never need to check it again. You will apply it to one famous problem, LeetCode 3, in two moves, meet the bugs that make that problem famous, and then generalise it in a third move.

This lesson builds on Foundation: Arrays & Strings: substrings versus subsequences, sets for "have I seen this before?", and dictionaries whose size is O(min(n, alphabet size)). Sliding Window Patterns introduces grow-and-shrink windows in general. Here you take one problem all the way down, then stretch it to its close variants. Code is Python 3. Throughout, n is len(s) and m is the size of the alphabet, meaning the number of different characters the input may contain.

Read the contract

LeetCode 3: Longest Substring Without Repeating Characters. Given a string s, return the length of the longest substring in which no character repeats. This lesson calls such a substring clean.

Three details of the contract matter:

• You return a length. "wke" and "kew" tie at 3, and you don't have to choose between them.
• A substring is contiguous. You may not skip characters.
• The limits: 0 <= len(s) <= 5 * 10^4, and s contains English letters, digits, symbols and spaces. So the empty string is a legal input, and in practice every character is printable ASCII, which has only 95 characters. That small alphabet matters more than you might expect.

Predict first: "pwwkew" contains p, w, k, e in that order, four different letters. Is the answer 4?

The slow way: one walk per start

The natural first solution tries every starting index and walks right until a character repeats:

def longest_by_walks(s):
    best = 0
    for start in range(len(s)):
        seen = set()
        for j in range(start, len(s)):
            if s[j] in seen:
                break                  # s[start..j] has a repeat; this walk is over
            seen.add(s[j])
        best = max(best, len(seen))    # seen = longest clean substring from start
    return best

It is correct, and it is short enough to trust. That makes it the reference you will test every faster version against. (An even slower version checks every pair (i, j) with len(set(s[i:j+1])). Building each set costs the substring's length, so that version is O(n³).)

What the walks repeat

Trace "abcdbef". Each row shows the characters one walk reads, including the repeat that stops it:

index:    0  1  2  3  4  5  6
s:        a  b  c  d  b  e  f
walk 0:   a  b  c  d  b            stops: b at 4 repeats b at 1   (clean length 4)
walk 1:      b  c  d  b            stops at the same b            (3)
walk 2:         c  d  b  e  f      reaches the end                (5)
walk 3:            d  b  e  f                                     (4)
walk 4:               b  e  f                                     (3)
walk 5:                  e  f                                     (2)
walk 6:                     f                                     (1)

That is 24 reads for a 7-character string, and the answer is 5. Walks 1 and 2 reread c and d, which walk 0 had already proved distinct.

Cost. Each walk reads at most n characters. It also reads at most m + 1, because a walk over an alphabet of m characters must hit a repeat by its (m + 1)-th character. So the walks take O(n · min(n, m)) time and O(min(n, m)) extra space.

🧠 The pigeonhole cap. A clean substring can never be longer than the alphabet. On LeetCode 3 (in practice at most 95 printable ASCII characters) each walk reads at most 96 characters, so even this slow version does at most 50,000 × 96 = 4,800,000 reads. The badge log has no such cap. Badge IDs are effectively an unlimited alphabet, so the walks can cost n(n+1)/2 reads. Before you trust or dismiss a complexity estimate, ask what m is.

Move 1: Slide a set window

Smell: each new start rereads a stretch that the previous walk already proved clean.

Keep what you proved

Predict first: the walk from index 0 in "abcdbef" stops at index 4 because b repeats. Which starts are finished without reading anything more? Where can the next candidate begin, and where does reading resume?

Turn that into code. Keep a window s[left..right] (both ends inclusive) that is always clean, and a set holding exactly its characters. Each new character enters on the right. If it is already in the set, evict characters from the left until its older copy is gone:

def longest_set_window(s):
    window = set()                 # the characters of s[left..right-1]
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in window:        # the old copy of ch is still inside
            window.remove(s[left])
            left += 1
        window.add(ch)             # s[left..right] is clean again
        best = max(best, right - left + 1)
    return best

Trace "abcabcbb":

At right = 6 the older b sits at index 4, one character in from the left edge. So the window must evict a and b before the incoming b fits. At right = 7 it evicts two characters again.

Why a left edge that only moves forward is enough

For each right, call the smallest l that makes s[l..right] clean the earliest clean start. Three facts do all the work:

1. Trimming keeps a clean string clean. If s[l..right] is clean, so is every shorter piece that ends at right. So the longest clean substring ending at right begins at the earliest clean start.
2. Growing never cleans a dirty string. If s[l..right] already holds a repeat, s[l..right+1] holds it too. So the earliest clean start never moves left as right grows, and left never has to go back.
3. The while loop stops exactly there. Before ch arrived the window was clean, so the only possible repeat is ch and its older copy. The window becomes clean at the moment that copy is evicted, and not before.

Every substring ends at some right, and the loop finds the best candidate for each one. Written as an invariant: after window.add(ch), window holds exactly the characters of s[left..right], and s[left..right] is the longest clean substring ending at right.

🧠 Fact 1 is what every "longest window" solution relies on: the rule survives trimming. When a rule does not survive trimming, a plain window stops working. The boss level at the end shows one.

Counting the work: a while inside a for

A loop inside a loop looks like O(n²). Don't judge it by its shape. Count how many times the inner body can run in the whole program instead.

Every pass through the while body moves left one step to the right. left starts at 0, never moves back, and can reach at most n. So the body runs at most n times in total over the entire run, not n times per character. Add the n calls to add and you get at most 2n set updates, each expected O(1). The whole function takes expected O(n) time. The set holds only the window's characters, which is O(min(n, m)) extra space.

Counting the evictions in real runs on 100,000 characters confirms it:

The count of evictions always equals the final value of left, because each eviction moves left once.

⚠️ "A while inside a for means O(n²)" is a myth. The real smell is an inner loop that starts over, like for j in range(start, n), which restarts for every start in the walks. An inner loop that only advances a pointer that never moves back is paid for once across the whole run. This way of counting is called amortized analysis: the total cost is bounded even when a single step is expensive.

Traps

• while, not if. One eviction is not always enough, as right = 6 above shows. With if, the set and the window stop agreeing. On "pwwkew", the second w evicts only the p, leaving two ws in the window, and the function returns 4.
• Evict first, then add. The add goes after the loop. Otherwise the new character is already in the set, and the membership check finds the character itself.
• Length is right - left + 1. The window is inclusive at both ends. Without the + 1 every non-empty answer comes out one too small.
• Empty input. On "" the loop never runs, and best stays 0, which is the correct answer.

Your turn: the clear-and-restart bug

A popular first attempt treats a repeat as a fresh start. It clears the set and begins a new window at the repeated character:

def longest_reset(s):
    window = set()
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in window:
            window.clear()
            left = right
        window.add(ch)
        best = max(best, right - left + 1)
    return best

It passes "abcabcbb", "bbbbb" and "pwwkew". Find a four-letter string where it fails, and say which of the three facts it breaks.

Move 2: Jump past the last-seen index

Smell: the eviction loop walks left forward one character at a time, only to find where the old copy of ch was. You could have written that position down when you first read it.

So keep a dictionary last that maps each character to the index where you most recently saw it. When ch arrives and its old copy is inside the window, the new left edge is last[ch] + 1, and one assignment replaces the whole eviction loop.

Predict first: try the obvious version on "abba". When ch is in last, it sets left = last[ch] + 1. What is left at right = 3, and what does the function return?

The fix is one function call:

def longest_jump(s):
    last = {}                  # char -> index of its most recent occurrence
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last:
            left = max(left, last[ch] + 1)   # jump forward, never back
        last[ch] = right                     # record AFTER reading the old value
        best = max(best, right - left + 1)
    return best

Trace "tmmzuxt", which has one real jump and one stale entry:

At right = 2 the old m at index 1 is inside the window, so left jumps to 2. At right = 6 the old t at index 0 is behind left, so max(2, 0 + 1) keeps left at 2, and the window grows to "mzuxt". Without max, left would drop back to 1 and the function would return 6.

The set forgets; the dictionary never does

The set window removes characters as left passes them, so it never holds a stale one. last is never cleaned. It holds every distinct character seen so far, not just the window's characters. In "tmmzuxt", after right = 5 it holds t, m, z, u and x while the window is "mzux": the t entry (index 0) is stale. On "abcdefghijzz" it ends with 11 entries while the window is just "z".

So last[ch] can point behind left. A stale copy is outside the window and cannot cause a repeat. max(left, last[ch] + 1) handles both cases:

• Old copy inside the window (last[ch] >= left): jump to last[ch] + 1.
• Old copy stale (last[ch] < left): then last[ch] + 1 <= left, and left stays where it is.

An equivalent guard is if last.get(ch, -1) >= left: left = last[ch] + 1. Either form is fine. The bare assignment is never fine. left works like a ratchet: it only turns forward, and max is what stops it slipping back.

Why the jump is exactly right. This is Move 1's fact 3 in one step. The window was clean before ch arrived, so the only possible repeat is ch itself. Of all the earlier copies of ch, the most recent one, at last[ch], is the closest to the window. If it is inside, the earliest clean start is last[ch] + 1. If it is not, no copy is inside and the start doesn't change.

Cost. Each character costs one lookup and one write, and there is no inner loop at all: expected O(n) time. last has one entry per distinct character seen, stale ones included, so it takes O(min(n, m)) extra space. That is the same bound as the set, for a different reason.

⚠️ Two more small bugs.

• Recording before checking. If last[ch] = right runs first, the check reads the index you just wrote. left becomes right + 1, every window is empty, and the function returns 0 on every input. This is the same order-of-operations rule as "check first, then add" from Foundation.
• Dropping the + 1. left = max(left, last[ch]) keeps the old copy inside the window. "aa" returns 2.

A fixed alphabet: an array instead of a dictionary

LeetCode 3's letters, digits, symbols and spaces are, in practice, all ASCII, with codes 0–127. A 128-slot list can replace the dictionary:

def longest_jump_ascii(s):
    last = [-1] * 128              # last[code] = latest index of chr(code); -1 = never seen
    left = 0
    best = 0
    for right, ch in enumerate(s):
        code = ord(ch)
        left = max(left, last[code] + 1)   # never seen: -1 + 1 = 0 <= left, no change
        last[code] = right
        best = max(best, right - left + 1)
    return best

The sentinel −1 removes the if. For a character never seen, last[code] + 1 is 0, and max leaves left alone. The table has 128 slots whatever n is, so it is O(1) extra space for this fixed alphabet, and each lookup is O(1) in the worst case, with no hashing involved.

⚠️ This works only for ASCII. ord('é') is 233, so last[233] raises IndexError. A Python str is indexed by Unicode code point, and there are 1,114,112 possible code points, so for general text keep the dictionary.

Which one should you write?

Both are linear. The jump saves at most n eviction steps, which is a constant-factor gain, not a better big-O. In an interview, write the version you can prove, and say why the other is also O(n).

Prove it before you trust it

Test every version against the slow walker on many small random strings, plus the edge cases:

import random

def check(trials=3000, max_len=10):
    cases = ["", "a", "aa", "ab", "abba", "dvdf", "tmmzuxt", "pwwkew", " ", "a b a"]
    for _ in range(trials):
        n = random.randint(0, max_len)
        cases.append("".join(random.choice("abcd ") for _ in range(n)))
    for s in cases:
        want = longest_by_walks(s)
        for f in (longest_set_window, longest_jump, longest_jump_ascii):
            assert f(s) == want, (f.__name__, s, f(s), want)
    print("all matched")

Success means check() prints all matched. The tiny alphabet "abcd " is deliberate. Random strings over a large alphabet rarely repeat, so they would barely exercise the eviction and jump logic.

Your turn: return the substring itself

Change longest_jump so it returns the first longest clean substring instead of its length. On "pwwkew" it should return "wke". Then: which single change makes it return "kew" instead?

def longest_clean_substring(s):
    last = {}
    left = 0
    best_start, best_len = 0, 0
    for right, ch in enumerate(s):
        if ch in last:
            left = max(left, last[ch] + 1)
        last[ch] = right
        if right - left + 1 > best_len:
            best_start, best_len = left, right - left + 1
    return s[best_start:best_start + best_len]

Move 3: When some repeats are allowed, count them

Smell: the rule tolerates repeats up to a limit, such as "at most k distinct characters" or "each value at most k times". A set cannot tell one b from two bs, the same reason a set cannot tell "aab" from "abb". There is also no single old copy to jump past.

The classic follow-up is LeetCode 340: Longest Substring with At Most K Distinct Characters. It is currently subscriber-only, as is its k = 2 special case, LeetCode 159. LeetCode 904: Fruit Into Baskets is free and is the same k = 2 problem told as a story: an array of fruit types, two baskets, the longest run using at most two types.

Predict first: on "eceba" with k = 2, the window "ece" is valid. Then b arrives, making three kinds. Which characters must leave, and what is the new window?

Replace the set with a dictionary of counts, and shrink while there are too many kinds:

def longest_k_distinct(s, k):
    counts = {}                    # char -> occurrences inside s[left..right]
    left = 0
    best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        while len(counts) > k:     # too many kinds: evict from the front
            out = s[left]
            counts[out] -= 1
            if counts[out] == 0:
                del counts[out]    # out has left the window completely
            left += 1
        best = max(best, right - left + 1)
    return best

Trace "eceba" with k = 2:

The function works unchanged on lists, so longest_k_distinct(fruits, 2) solves Fruit Into Baskets.

Why the del is not optional. len(counts) equals the number of kinds in the window only if every key still has a count of at least 1. Leave zero-count keys behind and len(counts) never shrinks. The loop keeps evicting, past right if need be, driving counts negative, until it touches a character that has no key (KeyError) or runs off the end (IndexError). On ("eceba", 2) it raises KeyError: 'a', because it tries to decrement a character it has not added yet.

Why it works. The same three facts hold. Trimming a window cannot add kinds, growing it cannot remove kinds, and the loop stops at the first start with at most k kinds. Each character is added once and evicted at most once, so the time is expected O(n). counts never holds more than k + 1 keys, and never more than m, so the extra space is O(min(k + 1, m)). With k = 0 every character is evicted as soon as it arrives, and the function returns 0.

Could you jump instead? Yes, but it takes more machinery. The character to drop is the one whose last occurrence inside the window is furthest left, so you need a structure ordered by last-seen index to find it. The counting window needs nothing new. Notice also that LeetCode 3 fits this template: it is the rule "each character at most once".

Your turn: at most k copies of each value

LeetCode 2958: Length of Longest Subarray With at Most K Frequency. Find the longest subarray in which no value appears more than k times. For nums = [1, 2, 3, 1, 2, 3, 1, 2] and k = 2 the answer is 6 ([1, 2, 3, 1, 2, 3]). Adapt the counting window. What is the shrink condition, and why is it enough to look at only one count?

def longest_at_most_k_copies(nums, k):
    counts = {}
    left = 0
    best = 0
    for right, x in enumerate(nums):
        counts[x] = counts.get(x, 0) + 1
        while counts[x] > k:           # only x can be over the limit
            counts[nums[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

The minimisation cousin of these problems, "the shortest window that contains all of these characters" (LeetCode 76: Minimum Window Substring), is taught in Sliding Window Patterns.

Final round: no label on the problem

Real problems don't say "use a window". For each one, find the rule, check whether it survives trimming, and decide what the window has to remember.

Challenge 1: the unique subarray with the biggest sum

LeetCode 1695: Maximum Erasure Value. nums holds positive integers (1 <= nums[i] <= 10^4, up to 10⁵ of them). Pick a subarray whose values are all distinct and maximise its sum. [4, 2, 4, 5, 6] gives 17 ([2, 4, 5, 6]). [5, 2, 1, 2, 5, 2, 1, 2, 5] gives 8 ([5, 2, 1] or [1, 2, 5]).

1. Which move applies, and what extra state does it need?
2. The best window here is the one with the biggest sum, not the longest one. Why is the earliest clean start still the right choice for each right?
3. Why would one walk per start be much slower here than on LeetCode 3?

def max_erasure_value(nums):
    window = set()
    left = 0
    total = 0                      # sum of nums[left..right]
    best = 0
    for x in nums:
        while x in window:
            window.remove(nums[left])
            total -= nums[left]
            left += 1
        window.add(x)
        total += x
        best = max(best, total)
    return best

Challenge 2: a repeat that is close by

LeetCode 219: Contains Duplicate II. Return True if two different indices i and j satisfy nums[i] == nums[j] and abs(i - j) <= k. [1, 2, 3, 1] with k = 3 gives True. [1, 0, 1, 1] with k = 1 gives True. [1, 2, 3, 1, 2, 3] with k = 2 gives False.

Which idea from this lesson answers it in one pass, and why is it enough to remember only one earlier index per value?

def contains_nearby_duplicate(nums, k):
    last = {}
    for i, x in enumerate(nums):
        if x in last and i - last[x] <= k:
            return True
        last[x] = i
    return False

Challenge 3 (boss level): a rule that breaks the window

LeetCode 395: Longest Substring with At Least K Repeating Characters. Find the longest substring in which every character appears at least k times. s is lowercase letters, 1 <= len(s) <= 10^4. "aaabb" with k = 3 gives 3 ("aaa"). "ababbc" with k = 2 gives 5 ("ababb").

Try to write a grow-and-shrink window. Find out why it fails, then find another way.

from collections import Counter

def longest_at_least_k(s, k):
    counts = Counter(s)
    rare = {ch for ch, c in counts.items() if c < k}
    if not rare:
        return len(s)              # every character already appears >= k times
    best = 0
    start = 0
    for i in range(len(s) + 1):
        if i == len(s) or s[i] in rare:
            best = max(best, longest_at_least_k(s[start:i], k))
            start = i + 1
    return best

Cheat sheet

Before moving on, open a blank editor and write longest_jump from memory. Then explain it aloud. What does left mean at the moment you compute the length? Why can last[ch] be stale, and what does max do about it? Why is the set version also O(n) despite its nested loop? Which input breaks clear-and-restart, and which breaks the missing max? Finally, name a rule that doesn't survive trimming and say what you would do instead.

Next: Hash Maps & Sets for counting, complement lookups and key design. Go back to Sliding Window Patterns for fixed-size windows, counting windows and Minimum Window Substring. See Maximum Subarray Sum for a problem where negative numbers break the window idea.