36. Longest Run of Unique Speaker Turns

Problem

A multi-party call transcript logs one speaker id per turn, in order — a support call with an agent, a customer, and an occasional supervisor barge-in, for example.

The longest contiguous run of turns with no repeated speaker is a cheap proxy for how long the conversation stays “in flow” before looping back to someone who already spoke in that stretch. Given the ordered list of speaker ids, return the length of that longest run.

Source: src/36_longest_unique_speaker_run.py

def longest_unique_speaker_run(turns: list[str]) -> int:
    ...

Examples:
>>> longest_unique_speaker_run(["A", "B", "A", "C", "B", "D"])
4

>>> longest_unique_speaker_run(["A", "A", "A"])
1

Step-by-Step Approach

1. Recognize this as “longest substring without repeating characters” with speaker ids standing in for characters — a classic variable-size sliding window.
2. Keep a window [left, right] that always contains no repeated speaker, and a map of each speaker's most recent index seen.
3. Advance right one turn at a time. If the current speaker was last seen at or after left, that's a repeat inside the current window — jump left to just past that earlier occurrence.
4. Record the current speaker's index in the last-seen map every iteration, whether or not it caused a jump.
5. Track the window length right - left + 1 after each step and keep the running maximum — that maximum is the answer once the loop ends.
6. Handle the empty-list edge case by returning 0 before (or instead of) entering the loop.

The key insight is that left only ever needs to jump forward when a repeat happens inside the current window — checking last_seen[speaker] >= left instead of unconditionally jumping on any prior sighting is what keeps the whole scan O(n) instead of accidentally O(n²).

Reference solution

def longest_unique_speaker_run(turns: list[str]) -> int:
    # sliding window with a last-seen-index map, O(n) time, O(distinct speakers) space
    last_seen: dict[str, int] = {}
    left = 0
    max_len = 0
    for right, speaker in enumerate(turns):
        # only shrink if the repeat is inside the current window
        if speaker in last_seen and last_seen[speaker] >= left:
            left = last_seen[speaker] + 1
        last_seen[speaker] = right
        max_len = max(max_len, right - left + 1)
    return max_len


TEST_CASES = [
    {"input": {"turns": ["A", "B", "A", "C", "B", "D"]}, "expected": 4},
    {"input": {"turns": ["A", "A", "A"]}, "expected": 1},
    {"input": {"turns": []}, "expected": 0},
    {"input": {"turns": ["A", "B", "C", "D"]}, "expected": 4},
    {"input": {"turns": ["A", "B", "B", "A"]}, "expected": 2},
    {"input": {"turns": ["A"]}, "expected": 1},
]


def main():
    for i, case in enumerate(TEST_CASES):
        turns = case["input"]["turns"]
        expected = case["expected"]
        print(f"Test {i}: longest_unique_speaker_run(turns={turns})")
        last_seen: dict[str, int] = {}
        left = 0
        max_len = 0
        for right, speaker in enumerate(turns):
            if speaker in last_seen and last_seen[speaker] >= left:
                left = last_seen[speaker] + 1
                print(f"  turn {right} repeats {speaker!r} inside window -> left moves to {left}")
            last_seen[speaker] = right
            max_len = max(max_len, right - left + 1)
            print(f"  turn {right}={speaker!r}: window=[{left},{right}] len={right - left + 1} max={max_len}")
        result = longest_unique_speaker_run(turns=turns)
        assert result == expected
        print(f"PASSED: {result}")
    print(f"All {len(TEST_CASES)} test cases passed.")


if __name__ == "__main__":
    main()

Key Functions & Tricks

• last_seen: dict[str, int] — maps each speaker id to the index it was last seen at
• last_seen[speaker] >= left — the guard that distinguishes an in-window repeat from a stale, already-evicted one
• left = last_seen[speaker] + 1 — shrinks the window to just past the earlier occurrence, never further
• max_len = max(max_len, right - left + 1) — running best window size, updated every step

How to Recognize This Pattern