Longest Distinct Run
Problem
Given a list of values, find the length of the longest contiguous stretch in which no value repeats. The stretch has to stay in one unbroken run, so you cannot skip over an element to avoid a repeat. Return 0 when the list is empty.
Examples
Input: items = [1, 2, 3, 2, 4, 5]
Output: 4
Why: the run 3, 2, 4, 5 has no repeatsInput: items = [7, 7, 7]
Output: 1
Why: every pair repeats, so a run of one is the best possibleInput: items = []
Output: 0
Why: edge case, there is no run at allHints
0 / 3
The answer is always a window that you can grow on the right and shrink on the left, never a scattered selection of elements.
When a repeat enters the window, the left edge has to jump past the earlier copy. To know where that copy was, remember the most recent position of every value.
Move the right edge one element at a time. If the incoming value was last seen at or after the current left edge, move the left edge just past that earlier position. Record the new position of the value and score the window length before continuing.
Solution
A window bounded by two indexes slides right while a map remembers where each value most recently appeared. When the incoming value already lives inside the window, the left edge jumps just past the earlier copy so the window stays repeat-free. Each element is visited once and the map lookups are constant time. Time is O(n), and space is O(d) where d is the number of distinct values.
def longest_distinct_run(items):
last_seen = {} # value -> most recent position
start = 0 # left edge of the current window
best = 0
for i, x in enumerate(items):
# a repeat inside the window drags the left edge past the old copy
if x in last_seen and last_seen[x] >= start:
start = last_seen[x] + 1
last_seen[x] = i
best = max(best, i - start + 1)
return best
print(longest_distinct_run([1, 2, 3, 2, 4, 5])) # -> 4
print(longest_distinct_run([7, 7, 7])) # -> 1
print(longest_distinct_run([])) # -> 0Stuck on the idea rather than the code? Sliding Window covers it.