Highlight Whole-Word Matches and Merge Overlapping Spans
Company: Harvey
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Highlight every whole-word occurrence of any supplied phrase in a text. Merge overlapping matched spans before inserting tags, so overlapping matches do not produce nested or duplicated highlight tags.
Implement `highlight_matches(text, phrases)`, with `text: string`, `phrases: string[]`, and return type `string`. Surround each merged span with the literal tags `<mark>` and `</mark>`.
### Constraints & Assumptions
- Matching is case-sensitive and uses exact phrase characters, including internal spaces.
- For this practice contract, word characters are ASCII letters, digits, and underscore. A phrase matches only when the character immediately before it, if any, and the character immediately after it, if any, are not word characters.
- Every phrase is nonempty and begins and ends with a word character. The text and phrases contain no `<` or `>` characters, so inserted tags cannot be confused with source text.
- `blue` does not match the prefix of `blueprint`. It does match in `blue sky` and `blue!`.
- Use half-open character intervals. Merge spans only when they overlap; exactly adjacent spans remain separate.
- Duplicate phrases or duplicate matches do not create additional tags.
- There are at most 10,000 text characters and 100 phrases, each at most 100 characters long. All characters are ASCII.
- These explicit boundary, case, tag, and adjacency rules resolve details not fixed in the report.
### Examples
```text
text = "blue sky and blueprint"
phrases = ["blue", "blue sky"]
result = "<mark>blue sky</mark> and blueprint"
```
```text
text = "red blue green"
phrases = ["red blue", "blue green"]
result = "<mark>red blue green</mark>"
```
```hint Keep positions in the original text
First collect and combine original-text spans. Inserting tags while still searching changes later character positions.
```
Overview: Highlight exact whole-word phrases, reject partial-word matches, merge overlapping text spans, and insert tags without shifting search positions.
Read the full Harvey Software Engineer interview experience this question came from
Highlight every whole-word occurrence of any supplied phrase in a text. Merge overlapping matched spans before inserting tags, so overlapping matches do not produce nested or duplicated highlight tags.
Implement `highlight_matches(text, phrases)`, with `text: string`, `phrases: string[]`, and return type `string`. Surround each merged span with the literal tags `<mark>` and `</mark>`.
### Constraints & Assumptions
- Matching is case-sensitive and uses exact phrase characters, including internal spaces.
- For this practice contract, word characters are ASCII letters, digits, and underscore. A phrase matches only when the character immediately before it, if any, and the character immediately after it, if any, are not word characters.
- Every phrase is nonempty and begins and ends with a word character. The text and phrases contain no `<` or `>` characters, so inserted tags cannot be confused with source text.
- `blue` does not match the prefix of `blueprint`. It does match in `blue sky` and `blue!`.
- Use half-open character intervals. Merge spans only when they overlap; exactly adjacent spans remain separate.
- Duplicate phrases or duplicate matches do not create additional tags.
- There are at most 10,000 text characters and 100 phrases, each at most 100 characters long. All characters are ASCII.
- These explicit boundary, case, tag, and adjacency rules resolve details not fixed in the report.
### Examples
```text
text = "blue sky and blueprint"
phrases = ["blue", "blue sky"]
result = "<mark>blue sky</mark> and blueprint"
```
```text
text = "red blue green"
phrases = ["red blue", "blue green"]
result = "<mark>red blue green</mark>"
```
```hint Keep positions in the original text
First collect and combine original-text spans. Inserting tags while still searching changes later character positions.
```
Constraints
- All characters are ASCII; text length is at most 10000 and neither text nor phrases contains < or >.
- At most 100 nonempty phrases, each at most 100 characters, beginning and ending with ASCII word characters.
- Word characters are ASCII letters, digits, underscore; case-sensitive exact matches require nonword characters or text edges immediately outside.
- Merge only overlapping half-open original-text spans; exactly adjacent spans stay separate and duplicates add no tags.
- Return text with each merged span enclosed in literal <mark> and </mark>, preserving all other characters.
Examples
Input: ('', [])
Expected Output: ''
Explanation: Empty text and phrases return empty text.
Input: ('plain words', [])
Expected Output: 'plain words'
Explanation: No phrases leave the text unchanged.