22. Longest Unique Topic Run

Problem

A stream of topic tags gets attached to consecutive messages in a customer conversation as Fin (or a human agent) works through it. The longest contiguous run with no repeated tag is a cheap proxy for how long the conversation stays "on one thread" before looping back to a topic it already touched on.

Given the list of tags in message order, return the length of the longest contiguous run that contains no duplicate tag.

Source: src/22_longest_unique_topic_run.py

def longest_unique_run(tags: list[str]) -> int:
    ...

>>> longest_unique_run(["billing", "account", "billing", "refund", "refund"])
3

>>> longest_unique_run(["a", "b", "c"])
3

>>> longest_unique_run([])
0

Step-by-Step Approach

1. Maintain a sliding window [start, i] over the tags that is guaranteed to contain no duplicates, plus a dict last_seen mapping each tag to the most recent index it appeared at.
2. Walk the list once with index i. For each tag, check whether it's already in last_seen and that previous occurrence is at or after start (still inside the current window).
3. If so, the window now contains a duplicate — shrink it by moving start to one past that previous occurrence, i.e. start = last_seen[tag] + 1.
4. Whether or not a shrink happened, record the tag's current index: last_seen[tag] = i.
5. Update the best answer with the current window length, i - start + 1.
6. After the loop, best holds the answer. An empty list naturally returns 0 since the loop body never runs.

The key insight is that the window start only ever moves forward, and it can jump directly to just past the conflicting duplicate instead of shrinking one element at a time — that's what keeps this O(n) rather than O(n²).

Reference solution

def longest_unique_run(tags: list[str]) -> int:
    # sliding window: on a repeat, jump the window start past the previous occurrence, O(n) time
    # tag -> most recent index seen, O(1) lookups
    last_seen: dict[str, int] = {}
    start = 0
    best = 0
    # (index, value) pairs, no manual counter
    for i, tag in enumerate(tags):
        # guard against stale (out-of-window) entries
        if tag in last_seen and last_seen[tag] >= start:
            # jump past duplicate instead of shrinking one at a time
            start = last_seen[tag] + 1
        last_seen[tag] = i
        # window length [start, i] inclusive
        best = max(best, i - start + 1)
    return best

Key Functions & Tricks

• enumerate(tags) — yields (index, value) pairs without manual counter or indexing.
• last_seen: dict[str, int] — tag → last index seen; O(1) lookups keep the scan O(n).
• last_seen[tag] >= start — stale-entry guard, confirms the duplicate is inside the window.
• start = last_seen[tag] + 1 — jump window start past the duplicate, O(n) not O(n²).
• max(best, i - start + 1) — running best of the current window length.

How to Recognize This Pattern