Quick Overview

This question evaluates skills in string matching, pattern recognition, overlap handling, text annotation, and counting occurrences across multiple source strings.

Handle multi-source string matching and tagging

Company: Harvey

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]).

Overview: 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

  1. Use a multi-pattern automaton (Aho-Corasick) to find all matches efficiently and count overlaps.
  2. Build a coverage array via a difference array to merge overlapping or touching matches into maximal regions.
  3. To annotate each region with source indices, sweep matches alongside regions and track active matches that overlap the region.

Loading coding console...

Show the approach

Approach

Build an Aho-Corasick automaton over sources to find all matches in a single left-to-right scan of output. For counting, increment counts[i] for each match of sources[i], allowing overlaps. For tagging, record each match interval [L,R) and build a difference array over character indices to compute a coverage count; coverage > 0 at position i means output[i] is covered by at least one match. Scan this coverage to produce maximal covered segments, merging overlapping or touching matches into one region. To annotate each region with source indices, sweep through the sorted matches while iterating over segments, maintaining a min-heap by match end and a multiset (via counts) of active matches. After adding matches with start < segment_end and removing matches with end <= segment_start, the keys of the active map are exactly the indices of sources whose matches overlap the segment. Emit each region as <tag>text</tag> followed by the sorted distinct indices in [i] form.

Time complexity:
O(n + sum_len + M log M), where n = len(output), sum_len = sum(len(s) for s in sources), and M is the number of matches
Space complexity:
O(sum_len + M + n)