16. Minimal Diff Between Successive Partial Transcript Hypotheses

Problem

A streaming STT model doesn't emit one final transcript — it emits a sequence of partial hypotheses that get revised, word by word, as more audio arrives, before locking in. A downstream consumer (a live caption UI, or an LLM tracking the conversation) shouldn't reprocess the whole transcript on every partial update; it just needs to know how much of the previous hypothesis is still valid and what changed after that point.

Given the previous partial transcript and the new one, each as a list of words, return the minimal patch: the length of their common prefix, and the words from the new transcript that come after it.

Source: src/16_partial_transcript_diff.py

def diff_transcript(previous_words: list[str], new_words: list[str]) -> tuple[int, list[str]]:

>>> diff_transcript(["I", "want", "a"], ["I", "want", "an", "apple"])
(2, ['an', 'apple'])

>>> diff_transcript(["hello"], ["hello", "world"])
(1, ['world'])

Step-by-Step Approach

1. Walk both word lists together with a single index i, starting at 0.
2. Advance i while i is within both lists' bounds and previous_words[i] == new_words[i] — this finds the longest common prefix in a single linear pass.
3. Stop as soon as the words diverge, or either list runs out — whichever comes first bounds how far the shared prefix can extend.
4. The final value of i is the common prefix length; no separate comparison pass is needed.
5. The patch to apply is simply everything in new_words from index i onward: new_words[i:]. Applying the patch means keeping previous_words[:i] as-is and replacing the rest with this slice.

The key insight is that finding a common prefix and computing the replacement tail are the same single linear scan, not two separate passes — the index where the scan stops is simultaneously the prefix length and the start of the slice that needs to be sent as the patch.

Reference solution

def diff_transcript(previous_words: list[str], new_words: list[str]) -> tuple[int, list[str]]:
    # two-pointer scan for the longest common prefix, O(min(len)) time
    i = 0
    limit = min(len(previous_words), len(new_words))
    while i < limit and previous_words[i] == new_words[i]:
        i += 1
    # everything after the shared prefix is the patch to apply
    return (i, new_words[i:])

Key Functions & Tricks

• min(len(a), len(b)) — bounds the scan so it never indexes past the shorter of the two lists.
• while i < limit and a[i] == b[i]: i += 1 — single linear pass that finds the common-prefix length directly, with no separate comparison step.
• new_words[i:] — slices the replacement tail using the exact same index the prefix scan stopped at.

How to Recognize This Pattern