Not the exercise, just the shape. This finds the best sum of three neighbouring numbers by adding the one that enters the window and subtracting the one that leaves, instead of adding three numbers every time.
sales = [4, 2, 7, 1, 8, 3]
window = sum(sales[:3]) # 4 + 2 + 7
best = window
for end in range(3, len(sales)):
window += sales[end] - sales[end - 3] # one in, one out
best = max(best, window)
print(best) # -> 16 (7 + 1 + 8)
- Reuse the work already done
The window keeps its total as it moves, so each step costs one addition and one subtraction, however wide the window is.
- Two edges, both moving forward
Here the window is a fixed width. In the exercise its width changes: the end moves every step, and the start moves only when a repeat forces it to. Neither ever moves back.
- What the window has to remember
For sums, a running total. For repeats, where each character was last seen, which is a dict from character to position.
Keep a window with a start and an end. Every step the end moves on by one. When does the start have to move, and to where?
Keep a dict of where each character was last seen. When the new character was last seen inside the current window, the start has to move to just after that position.
for end, char in enumerate(text): if char was seen at or after start, move start to its last position + 1. Record the new position, then compare end - start + 1 with the best so far.
def longest_unique_run(text): last_seen = {} start = best = 0 for end, char in enumerate(text): if char in last_seen and last_seen[char] >= ____: start = last_seen[char] + 1 last_seen[char] = ____ best = max(best, end - start + ____) return best
def longest_unique_run(text):
last_seen = {} # character -> position it was last seen
start = best = 0
for end, char in enumerate(text):
if char in last_seen and last_seen[char] >= start:
start = last_seen[char] + 1
last_seen[char] = end
best = max(best, end - start + 1)
return best
A character seen before the window started is not a repeat any more. Without that check the start can move backwards, and "abba" comes out as 3.
Comparing only when a repeat is found misses a stretch that runs to the end of the string, which is the whole answer for a word with no letter repeated.
That both edges only move forward, so each character is added once and passed once: linear time. The dict is at most one entry per distinct character.
If the question changes to "at most k distinct characters", the positions dict is not enough; you keep counts in the window and shrink from the start while there are too many. The window survives, what it remembers changes.
- Return the stretch itself, not its length, and decide which one wins a tie.
- Allow each character at most twice.
- Find the longest stretch with at most k different characters.