Add Bold Tag in String

How it works

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 at the start of a bold region and at the end, which handles merging automatically.

Steps

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 ``.
   • Append the character s[i].
   • If bold[i] is true and either i == n-1 or bold[i+1] is false, insert ``.
4. Return the result string.

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 × (n^2 × k - n × k^2))
• Space complexity: O(n)

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

Things to watch for

Not Merging Adjacent Bold Regions

A common mistake is inserting separate `` tags for each word match without merging overlapping or adjacent regions. For example, if "ab" and "bc" both match in "abc", the result should be abc, not abbc.

Off-by-One When Marking Bold Ranges

When marking character positions as bold, forgetting that the end index should be start + len(word) - 1 (inclusive) or using start + len(word) (exclusive) inconsistently leads to incorrect bold boundaries.

Missing Overlapping Occurrences of the Same Word

Using find() with start + len(word) as the next search position misses overlapping matches. For example, searching for "aa" in "aaa" should find two matches (at index 0 and 1), but skipping by word length finds only one.

from typing import List

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)

class Solution {
public:
    string addBoldTag(string s, vector<string>& words) {
        int n = s.size();
        vector<bool> bold(n);
        
        for (string word: words) {
            int start = s.find(word);
            while (start != -1) {
                for (int i = start; i < start + word.size(); i++) {
                    bold[i] = true;
                }
                
                start = s.find(word, start + 1);
            }
        }
        
        string openTag = "<b>";
        string closeTag = "</b>";
        string ans = "";
        
        for (int i = 0; i < n; i++) {
            if (bold[i] && (i == 0 || !bold[i - 1])) {
                ans += openTag;
            }
            
            ans += s[i];
            
            if (bold[i] && (i == n - 1 || !bold[i + 1])) {
                ans += closeTag;
            }
        }
        
        return ans;
    }
};