Problem Description

You are given a list of strings words and a string s. Your task is to wrap substrings in s that match any word in words with bold tags <b> and </b>. If two bolded substrings overlap or are consecutive, you should merge them into a single bolded substring.

For example, if words = ["ab", "bc"] and s = "aabcd", then both "aabcd" and "aabcd" are possible, but you must ensure all possible substrings are merged and bolded together if overlapping or adjacent.

• Each word in words can be used multiple times and may overlap.
• The input string s consists of lowercase English letters.
• Return the string with the minimum number of <b> tags such that all substrings matching any word in words are bolded.

Thought Process

The naive approach is to check every substring of s to see if it matches any word in words. For each match, mark the corresponding substring as bold. However, this would be inefficient for large s or many words.

To optimize, we realize that we need to efficiently find all occurrences of each word in words within s. Once we know which intervals of s should be bolded, we can merge overlapping or adjacent intervals and insert the bold tags.

The main challenge is:

• Efficiently marking all positions in s that should be bolded.
• Correctly merging overlapping or adjacent bold intervals.
• Constructing the result string with the minimum number of bold tags.

Solution Approach

We can solve the problem in the following steps:

1. Mark bold positions:
   • Create a boolean array bold of the same length as s, initialized to False.
   • For each word in words, iterate through s and mark positions that are part of a match as True in bold.
2. Merge intervals:
   • Since overlapping or adjacent matches should be merged, the bold array naturally represents merged intervals.
3. Build the result string:
   • Iterate through s and use the bold array to determine where to insert <b> and </b> tags.
   • Open a bold tag when entering a bold region, and close it when leaving.
4. Return the constructed string.

Why a boolean array? Using a boolean array allows us to efficiently mark and merge all intervals where a word is found, without explicitly storing start and end indices for each interval.

Alternative: For very large words lists, a Trie could speed up the matching step, but for most constraints, the above approach is sufficient.

Example Walkthrough

Suppose words = ["ab", "bc"] and s = "aabcd".

1. Mark bold positions:
   • For "ab": found at index 1 ("ab" in "aabcd"), so mark bold[1] and bold[2] as True.
   • For "bc": found at index 2 ("aabbcd"), so mark bold[2] and bold[3] as True.
   • Final bold array: [False, True, True, True, False]
2. Build result string:
   • At index 0: not bold, output 'a'
   • At index 1: start of bold region, insert <b> before 'a'
   • Continue through indices 2 and 3 (still bold).
   • At index 4: end of bold region, insert </b> before 'd'
   • Result: a<b>abc</b>d

This example shows how overlapping matches ("ab" and "bc") are merged into a single bold region.

Time and Space Complexity

Brute-force approach:

• Checking every substring of s against every word is O(N^2 * K), where N is the length of s and K is the number of words.

• For each word, we scan s in O(N) time, so total time is O(N * W * L), where W is the number of words and L is the average word length.
• Marking bold regions and building the result string is O(N).
• Space complexity is O(N) for the bold array and the output string.

If a Trie is used for matching, the preprocessing is O(total characters in words), and searching is O(N * max_word_length).

Summary

The key insight is to efficiently mark all regions of s that should be bolded, using a boolean array to merge overlapping and adjacent intervals. By scanning through s and marking matches, then constructing the output with minimal bold tags, we achieve a clean and optimal solution. This approach is both intuitive and efficient for typical input sizes.

Code Implementation

class Solution:
    def boldWords(self, words, s):
        n = len(s)
        bold = [False] * n
        for word in words:
            start = s.find(word)
            while start != -1:
                for i in range(start, start + len(word)):
                    bold[i] = True
                start = s.find(word, start + 1)
        res = []
        i = 0
        while i < n:
            if not bold[i]:
                res.append(s[i])
                i += 1
            else:
                res.append('<b>')
                while i < n and bold[i]:
                    res.append(s[i])
                    i += 1
                res.append('</b>')
        return ''.join(res)
      

class Solution {
public:
    string boldWords(vector<string>& words, string s) {
        int n = s.size();
        vector<bool> bold(n, false);
        for (const string& word : words) {
            size_t pos = s.find(word);
            while (pos != string::npos) {
                for (int i = pos; i < pos + word.size(); ++i)
                    bold[i] = true;
                pos = s.find(word, pos + 1);
            }
        }
        string res;
        int i = 0;
        while (i < n) {
            if (!bold[i]) {
                res += s[i++];
            } else {
                res += "<b>";
                while (i < n && bold[i]) {
                    res += s[i++];
                }
                res += "</b>";
            }
        }
        return res;
    }
};
      

class Solution {
    public String boldWords(String[] words, String s) {
        int n = s.length();
        boolean[] bold = new boolean[n];
        for (String word : words) {
            int start = s.indexOf(word);
            while (start != -1) {
                for (int i = start; i < start + word.length(); ++i)
                    bold[i] = true;
                start = s.indexOf(word, start + 1);
            }
        }
        StringBuilder res = new StringBuilder();
        int i = 0;
        while (i < n) {
            if (!bold[i]) {
                res.append(s.charAt(i++));
            } else {
                res.append("<b>");
                while (i < n && bold[i]) {
                    res.append(s.charAt(i++));
                }
                res.append("</b>");
            }
        }
        return res.toString();
    }
}
      

var boldWords = function(words, s) {
    const n = s.length;
    const bold = new Array(n).fill(false);
    for (const word of words) {
        let start = s.indexOf(word);
        while (start !== -1) {
            for (let i = start; i < start + word.length; ++i)
                bold[i] = true;
            start = s.indexOf(word, start + 1);
        }
    }
    let res = '';
    let i = 0;
    while (i < n) {
        if (!bold[i]) {
            res += s[i++];
        } else {
            res += '<b>';
            while (i < n && bold[i]) {
                res += s[i++];
            }
            res += '</b>';
        }
    }
    return res;
};