Longest Unique Substring

The Idea

Keep a window that holds only distinct characters, plus a set of what is inside it. The right edge always advances.

When the incoming character is already in the set, pull the left edge in — dropping characters — until the duplicate is gone. The longest width you ever saw is the answer.

Real-World Example

Streaming deduplication works this way. A telemetry pipeline keeps the longest recent run of distinct device IDs in memory; when an ID repeats, it forgets everything up to the previous sighting instead of rescanning the whole buffer.

The Code

def longest_unique(s):
    seen = set()
    left = best = 0
    for right, ch in enumerate(s):
        while ch in seen:           # shrink until ch is free again
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))   # 3  -> "abc"
print(longest_unique("bbbbb"))      # 1

s = "abba"
seen, left, best = set(), 0, 0
for right, ch in enumerate(s):
  while ch in seen:
      seen.remove(s[left])
      left += 1
  seen.add(ch)
  best = max(best, right - left + 1)
print(best)