mycsmajor
Data structures problem 23 of 30

Longest substring without repeats

  • Data structures
  • Medium

Write longest_unique(s) that returns the length of the longest run of consecutive characters in s with no character repeated.

longest_unique("abcabcbb")   # 3  ("abc")
longest_unique("bbbbb")      # 1
longest_unique("pwwkew")     # 3  ("wke")
longest_unique("")           # 0
Show hint

Keep a window [start, i] with no repeats. Remember the last index where each character appeared, so you can jump start forward when a repeat enters.

Show solution 
def longest_unique(s):
    last_seen = {}
    start = best = 0
    for i, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = i
        best = max(best, i - start + 1)
    return best

The check last_seen[ch] >= start matters: a character seen before the current window is not a repeat inside it. Both ends of the window only move forward, so this is O(n), compared with O(n2) or worse for checking every substring.

Want a problem like this every day? See today's problem and keep a streak going.