Longest substring without repeated code points
IntermediateJunior · 1–3 yearsSliding window
Python 3.10+; standard library only. GIL discussion refers to conventional CPython builds, not optional free-threaded builds.
Problem statement
Return the length of the longest contiguous substring with unique code points.
Find a maximal non-repeating segment in a token stream.
Input: Python str.
Output: Integer length.
- 0 <= n <= 100000.
- Case sensitive; count code points.
Sample 1
Input: abcabcbb Output: 3
abc has length three.
Sample 2
Input: bbbbb Output: 1
Any two adjacent b characters repeat.
Brute-force solution
For each start, extend a set until repetition and retain the longest segment.
O(n²) time, O(n) space.
def longest_unique_slow(text):
best=0
for i in range(len(text)):
seen=set()
for ch in text[i:]:
if ch in seen: break
seen.add(ch);best=max(best,len(seen))
return bestOptimized solution
Track last positions; jump the left boundary forward when the repeated character lies in the current window.
- Maintain a valid unique window.
- Move left to max(left,last[ch]+1).
- Update best and last position.
def longest_unique(text):
last={};left=best=0
for right,ch in enumerate(text):
left=max(left,last.get(ch,-1)+1)
best=max(best,right-left+1)
last[ch]=right
return best
print(longest_unique("abcabcbb"))
Complexity analysis
Time: O(n) expected.
Auxiliary space: O(min(n, alphabet size))
Test cases
- Empty string.
- Repeat outside the current window.
assert longest_unique("abcabcbb")==3
assert longest_unique("bbbbb")==1
assert longest_unique("abba")==2
assert longest_unique("")==0Common mistakes
- Moving left backward for an old duplicate.
- Solving subsequence instead of substring.
Key takeaways
- Left never moves backward.
- Keep the window invariant.
- Last indices avoid repeated removal.
Follow-up challenges
- How would you return the substring?
- How do you count grapheme clusters?