Add Bold Tag in String
Medium · Intervals · Array · Hash Table · String · Trie · String Matching
Problem
You are given a string s and an array of strings words. Every occurrence of any word from words inside s must be shown in bold, by wrapping it with and .
If two bold substrings overlap, or are directly adjacent (one ends right where the next begins), combine them under a single pair of tags. Return s after inserting the tags.
Examples
Input: s = "hellothere", words = ["llo","the"] Output: "he<b>llothe</b>re"
"llo" ends at index 4 and "the" starts at index 5, so the two bold stretches touch and share one pair of tags.
Input: s = "aaab", words = ["aa","c"] Output: "<b>aaa</b>b"
"aa" matches at indices 0 and 1; the overlapping matches cover "aaa". "c" never occurs.
Input: s = "xyz", words = ["q"] Output: "xyz"
Nothing is bold, so the string is unchanged.
Constraints
- 1 <= len(s) <= 1000
- 0 <= len(words) <= 100
- 1 <= len(words[i]) <= 1000
- s and words[i] consist of English letters and digits.
- All values of words are unique.
Approaches
- Baseline: collect every occurrence, merge intervals — time O(W · n · L + k log k), space O(k)
Follow-up
Rendering is easy once the bold characters are known; the work is finding the matches. With many long words, Aho-Corasick finds every occurrence in O(n + Σ|w| + matches). Could the trie walk in the main solution ever be slower than that?
Related problems
Start free on Cariara · Coding problems · System design studio
