The problem asks us to find every occurrence of every word from words inside s, then bold those portions. Finding the matches is plain substring search. The harder requirement is the merging: if "aa" matches at positions 0-1 and 1-2, the two matches overlap and must sit inside a single <b>...</b> pair, not two. If one match ends exactly where another begins, the adjacent regions must also share one pair of tags.

This splits the work into two steps: decide which characters of s need to be bold, then group consecutive bold characters and wrap each group with one pair of tags.

Key Constraints:

Intuition

Find every occurrence of every word in s, record the interval [start, end) for each match, merge overlapping or adjacent intervals, and wrap each merged region in bold tags. This is the merge intervals pattern: sort the match intervals by start position, then sweep through them, extending the current region whenever the next interval starts at or before its end. Using start <= end (rather than strict <) is what folds adjacent matches into one region.

Algorithm

Visualization and Code

The sorting and merging steps can be removed entirely. The next approach marks each character position as bold directly, and a single scan over those marks produces the merged regions.

Intuition

Instead of collecting intervals and merging them, we use a boolean array bold of the same length as s. For each word in words, we find every occurrence in s and mark the covered positions as true. Once all words have been processed, we scan the bold array and insert <b> at every transition from false to true and </b> at every transition from true to false.

No sorting or merging is needed. Overlapping matches mark some positions twice, and setting an already-true entry to true changes nothing. Adjacent matches leave no false entry between them, so they form one contiguous run of true values, and the transition scan wraps that run in a single pair of tags.

Algorithm

Visualization and Code

The marking step still searches the string once per word. The final approach replaces those per-word scans with a single Trie walk from each starting position.

Intuition

Checking each word independently repeats work whenever words share prefixes: matching "abc" and "abd" at the same position compares "ab" twice. A Trie (prefix tree) built from the words checks all of them in one pass. Starting from position i, walk the Trie character by character; every node that marks the end of a word means that word matches at i. Track the farthest end among those matches and mark bold[i..farthestEnd-1] as true. Marking only up to the farthest end is enough because every shorter match starting at i covers a prefix of that same range.

This reduces the matching step from O(n m k) to O(n * W), where W is the length of the longest word.

Algorithm

Visualization and Code