Handle multi-source string matching and tagging
Company: Harvey AI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
Given an LLM output string and a list of source strings, design an algorithm to count how many times each source appears in the output. Extend the solution to return the output string where every occurrence of a source string is wrapped in <tag></tag> while correctly handling overlapping matches. Modify the algorithm so that each tag also includes annotations of the indices of the sources that matched (e.g., <tag>text</tag>[1][3]).
Quick Answer: This question evaluates skills in string matching, pattern recognition, overlap handling, text annotation, and counting occurrences across multiple source strings.
Given a string output and a list of source strings sources, return two results: (1) counts: a list where counts[i] is the number of occurrences (allowing overlaps) of sources[i] in output; (2) tagged: a new string constructed by wrapping each maximal contiguous region of output that is covered by at least one match with <tag> and </tag>. After each such tag, append bracketed source indices in ascending order (e.g., [0][3]) indicating all distinct i for which at least one occurrence of sources[i] overlaps that region. Indices are 0-based. Overlapping or touching matches are merged into a single tagged region. Matching is exact and case-sensitive.
Constraints
- 1 <= len(output) <= 200000
- 1 <= len(sources) <= 5000
- 1 <= sum(len(s) for s in sources) <= 200000
- All sources[i] are non-empty; duplicates allowed
- Matching is exact and case-sensitive
- Indices in annotations are 0-based, unique per region, and sorted ascending
Hints
- Use a multi-pattern automaton (Aho-Corasick) to find all matches efficiently and count overlaps.
- Build a coverage array via a difference array to merge overlapping or touching matches into maximal regions.
- To annotate each region with source indices, sweep matches alongside regions and track active matches that overlap the region.