1. Mark Bold Characters

Intuition

The key insight is that we need to track which characters should be bold, not which substrings. If we find all occurrences of each word in the string and mark every character position that falls within any match, we can then merge overlapping or adjacent bold regions naturally.

We use a boolean array where each index corresponds to a character in the string. For every word, we find all its occurrences and mark the corresponding positions as bold. When building the result, we only insert <b> at the start of a bold region and </b> at the end, which handles merging automatically.

Algorithm

1. Create a boolean array bold of size n (length of string s), initialized to false.
2. For each word in the dictionary:
   • Find all occurrences of the word in s.
   • For each occurrence starting at index start, mark bold[i] = true for all i from start to start + len(word) - 1.
3. Build the result string by iterating through s:
   • If bold[i] is true and either i == 0 or bold[i-1] is false, insert <b>.
   • Append the character s[i].
   • If bold[i] is true and either i == n-1 or bold[i+1] is false, insert </b>.
4. Return the result string.

class Solution:
    def addBoldTag(self, s: str, words: List[str]) -> str:
        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)

        open_tag = "<b>"
        close_tag = "</b>"
        ans = []
        
        for i in range(n):
            if bold[i] and (i == 0 or not bold[i - 1]):
                ans.append(open_tag)
                
            ans.append(s[i])
            
            if bold[i] and (i == n - 1 or not bold[i + 1]):
                ans.append(close_tag)
        
        return "".join(ans)

Time & Space Complexity

The time complexity may differ between languages. It is dependent on how the built-in method is implemented.
For this analysis, we will assume that we are using Java.

• Time complexity: $O(m \cdot (n^2 \cdot k - n \cdot k^2))$
• Space complexity: $O(n)$

Where $n$ is s.length, $m$ is words.length, and $k$ is the average length of the words.