Highlight Overlapping Phrases in a Sentence

Problem Statement

In legal analysis and document review, software systems frequently search large documents for key phrases and present the results with matched keywords highlighted. When multiple search terms match overlapping or adjacent spans of text, naive tag insertion produces invalid, redundant, or malformed tags (e.g., quick brown fox).

Implement a function highlight_phrases that takes an input string text, a list of search phrases phrases, and custom tag markers open_tag and close_tag. The function must return a new string where every character covered by an exact match of at least one phrase is enclosed within the tag markers. Overlapping or contiguous highlighted spans must be merged into a single pair of tags.

Function Signature

def highlight_phrases(
    text: str, 
    phrases: list[str], 
    open_tag: str = "", 
    close_tag: str = ""
) -> str:
    pass

Requirements & Invariants

1. Exact Matching: Matches are case-sensitive and must match characters exactly.
2. Tag Merging: If two matched spans overlap (e.g., [4, 15] and [10, 20]) or are directly adjacent (e.g., [4, 10] and [10, 20]), they must be combined into a single highlighted interval [4, 20] with one opening tag and one closing tag.
3. No Redundant Tags: Empty phrases or zero-length matches must not introduce empty tags like ``.

Constraints

• len(text) <= 100,000
• 1 <= len(phrases) <= 1,000
• 1 <= len(p) <= 500 for each p in phrases
• All inputs contain standard printable ASCII/Unicode characters.

Examples

Example 1:

text = "The quick brown fox jumps over the lazy dog."
phrases = ["quick brown", "brown fox jumps"]
open_tag = ""
close_tag = ""

# Output:
# "The quick brown fox jumps over the lazy dog."

Explanation: "quick brown" covers indices [4, 15]. "brown fox jumps" covers indices [10, 25]. The merged interval is [4, 25].

Example 2:

text = "banana"
phrases = ["an", "na"]
open_tag = "["
close_tag = "]"

# Output:
# "b[anana]"

Explanation: "an" matches at [1, 3] and [3, 5]. "na" matches at [2, 4] and [4, 6]. All intervals merge into [1, 6].