← Python roadmap

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 best
Optimized solution

Track last positions; jump the left boundary forward when the repeated character lies in the current window.

  1. Maintain a valid unique window.
  2. Move left to max(left,last[ch]+1).
  3. 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("")==0
Common 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?