Problem Statement

Create this function:

def highlight_matches(document: str, sources: list[str]) -> str:
    pass

A phrase is considered a match only when its entire text appears in document with valid word boundaries.

For this task:

• Matching distinguishes uppercase and lowercase letters. Whether a case-insensitive variant should instead be used is an interviewer decision to clarify.
• Each source contains at least one character, and its first and last characters are letters or digits.
• The phrase must be bounded by word boundaries. Thus, "blue" does not match the occurrence of those letters within "blueprint".
• A single source can be found more than once.
• Different matches are allowed to overlap.
• Adjacency may also be part of the interview discussion. Here, two matches count as adjacent when only whitespace separates their character ranges.
• Preserve the document exactly as supplied, including case, punctuation, and whitespace.

Produce the original document with each combined matching span enclosed by <yellow> and </yellow>.

Example

document = "The quick brown fox jumps over the lazy dog."
sources = ["quick brown", "brown fox jumps"]

highlight_matches(document, sources)
# Returns:
# "The <yellow>quick brown fox jumps</yellow> over the lazy dog."

The phrases share the word "brown", so their overlapping ranges are emitted as one highlighted span.

Edge Cases

• With document = "blueprint" and sources = ["blue"], nothing is highlighted because "blue" is not a whole word there.
• When a source occurs repeatedly, each occurrence is treated as its own match.
• Repeated strings in sources remain distinct sources because citation identity is based on the positions in the input list.
• When there are no matches, return document without modification.

Follow-Up Prompt

Modify the implementation so that every highlighted span records which sources helped create it.

For each source, do the following:

1. Tally every valid occurrence in the complete document. The tally is document-wide rather than restricted to one highlighted span.
2. For each merged span, gather the indices of sources having at least one match within that span.
3. Sort those source indices by decreasing document-wide occurrence count. The tie rule is specified here as ascending source index.
4. After the closing highlight tag, write each zero-based source index in the form [source_id].

Return the tagged text, the count for every source, and the citation list associated with each highlighted span.

from dataclasses import dataclass


@dataclass
class CitationResult:
    tagged_document: str
    counts: dict[int, int]
    citations: list[list[int]]


def highlight_with_citations(
    document: str,
    sources: list[str],
) -> CitationResult:
    pass

Example

document = "The quick brown fox jumps over the quick blue fox."
sources = [
    "quick brown", # source 0, one occurrence
    "brown fox jumps", # source 1, one occurrence
    "quick", # source 2, two occurrences
    "blue", # source 3, one occurrence
]

result = highlight_with_citations(document, sources)

result.tagged_document
# "The <yellow>quick brown fox jumps</yellow>[2][0][1] over the "
# "<yellow>quick blue</yellow>[2][3] fox."

result.counts
# {0: 1, 1: 1, 2: 2, 3: 1}

result.citations
# [[2, 0, 1], [2, 3]]

Source 2 comes first in both citation arrays because its global frequency is higher. The remaining sources have equal frequencies, so their smaller input indices come first.