The problem
Given a string, find the length of the longest stretch of consecutive characters with no repeated letter.
Input: "abcabcbb"
Output: 3 ("abc")Picture it
Picture yourself looking out of a train window at a street of shop signs, one letter per shop. The window can stretch and shrink. Its right edge moves forward one shop at a time. If the new letter is already somewhere inside the window, the left edge jumps just past that earlier copy, so the window again has only unique letters. We record the widest window we ever had.
How to recognise it
- The answer is a substring (a contiguous run of characters), not a subsequence where you may skip characters.
- You want the longest (or shortest) run that satisfies a rule, here "no character appears twice".
- The rule is monotone: if a window breaks it, every bigger window containing it breaks it too. So you can grow on the right and shrink on the left.
- The rule depends on what is inside the window, which a dictionary can track as it moves.
- Lengths up to about 5 × 10^4 rule out checking every substring.
Start with brute force
From every starting position, extend to the right with a set of letters seen so far, and stop at the first repeat. The longest run found is the answer.
def longest_brute(s):
best = 0
for i in range(len(s)):
seen = set()
for j in range(i, len(s)):
if s[j] in seen:
break
seen.add(s[j])
best = max(best, len(seen))
return best
Time is O(n · m), where m is the length of the answer (at most n). When most characters differ, as in long Unicode text, that is O(n²): for n = 5 × 10^4 about 1.25 × 10^9 steps. Space is O(m) for the set.
From brute force to the idea
- Find the waste. After a repeat, the next start throws the set away and re-reads characters it has just checked.
- Keep the window. Hold a window from
lefttorightthat always has unique letters.rightmoves forward one character at a time. - Fix a repeat by moving
left. If the new characterchis already inside the window, any window starting at or before that earlier copy containschtwice. Soleftjumps to just past it. - Remember positions. A dictionary
lastmaps each letter to where it last appeared, so the jump is one lookup, not a scan. - Ignore copies outside the window. A letter can be in
lastbut sit left ofleft. That is why the code checkslast[ch] >= leftbefore jumping. - Record the best. After each step the window
right - left + 1is valid, so compare it with the best so far.
This is the key idea: a sliding window plus a "last seen position" dictionary, with the left edge jumping past the old copy.
The key idea
Sliding window + “last seen position” dictionary: when a repeat appears, jump the left edge past the old copy. O(n).
Python solution
def longest_unique(s):
last = {} # letter -> last position
left = best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1
last[ch] = right
best = max(best, right - left + 1)
return bestIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n · m), up to O(n²): each start re-scans up to m characters | O(m): the set holds one run |
| Sliding window (shown code) | O(n): right visits each character once and left only moves forward | O(k): one entry per distinct character, k ≤ n |
Edge cases
- Empty string: the loop never runs and the code returns 0.
- One character (
"a"): returns 1. - All the same (
"bbbbb"):leftfollowsright, so the answer is 1. - Old copy outside the window (
"abba"): returns 2. Without thelast[ch] >= leftcheck, the secondawould moveleftbackwards and the code would wrongly return 3. - Spaces, digits and case: every character counts, and
"a"differs from"A"."aA"returns 2 and"a b c a"returns 3 (the space repeats). - Answer at the very end (
"tmmzuxt"): returns 5 becausebestis updated on every step, not only when a repeat appears.
Common mistakes
- Dropping the
last[ch] >= leftcheck, soleftjumps backwards on strings like"abba". - Updating
bestonly when a repeat is found, which misses a longest run that reaches the end of the string. - Clearing a set on a repeat, which forgets the letters between the old copy and the new one.
Find the length of the longest substring that contains at most two distinct characters. For "eceba" the answer is 3 ("ece"), and for "ccaabbb" it is 5 ("aabbb"). Describe your approach, then write it if you like.
Compare with our answer
Same window, different rule. Grow right and count letters inside the window. When there are more than two kinds, shrink from the left one step at a time until two remain. A single jump does not work, because you do not know in advance how far left must move.
def longest_two_distinct(s):
count = {} # letter -> how many times inside the window
left = best = 0
for right, ch in enumerate(s):
count[ch] = count.get(ch, 0) + 1
while len(count) > 2: # too many kinds: shrink from the left
out = s[left]
count[out] -= 1
if count[out] == 0:
del count[out]
left += 1
best = max(best, right - left + 1)
return best
Time O(n), because each character enters and leaves the window at most once. Space O(1) here, as the dictionary never holds more than three keys.
A strong answer mentions: counts instead of last positions, deleting a letter when its count reaches 0, and why the inner while loop does not make it O(n²).
1. Given a list of positive numbers, find the shortest contiguous run whose sum is at least a target. Which approach fits?
The run is contiguous and, with positive numbers, adding makes the sum bigger and removing makes it smaller, so the window can grow and shrink. Sorting breaks contiguity, and prefix-sum lookups need an exact target, not "at least".
2. Why is the shown solution O(n) even though left can jump many places at once?
There is one loop over the string and every step does constant work: a lookup, an assignment and a comparison. The alphabet is not limited to 26 letters, and the dictionary is never reset.
3. A learner deletes and last[ch] >= left from the shown code. What does it return for "abba"?
At the last a, last['a'] is 0, so left becomes 1, behind its current value of 2. The window "bba" then counts as length 3. The correct answer is 2.
Score 60% or more and the lesson is marked complete.