# 616 Add Bold Tag in String

Given a string s and a list of strings dict, you need to add a closed pair of bold tag \<b> and \</b> to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

**Example 1:**

```
Input: 
s = "abcxyz123"
dict = ["abc","123"]
Output:
"<b>abc</b>xyz<b>123</b>"
```

**Example 2:**

```
Input: 
s = "aaabbcc"
dict = ["aaa","aab","bc"]
Output:
"<b>aaabbc</b>c"
```

**Note:**

1. The given dict won't contain duplicates, and its length won't exceed 100.
2. All the strings in input have length in range \[1, 1000].

**The Idea:** Although I have not approached the problem in the same way, this problem is identical to merge intervals. Each substring that is in the dictionary creates an interval in s. Each interval has a start and end point, and this problem can be reduced to merging all these intervals together and inserting a `<b>` and `</b>` tag at the start and end of each interval respectfully.

The approach I took included a boolean array. For each word in the dictionary that exists in the substring s, we mark it as active in the boolean array. A trie also works for this. The boolean array will naturally merge intervals on its own. Then in the final step, append opening and closing tags at the start and end of each active interval.

**Complexity:** O(n\*m) time where n is the size of s and m is the number of words in the dictionary. O(|S|) space

```python
class Solution:
    def addBoldTag(self, s, dict):
        """
        :type s: str
        :type dict: List[str]
        :rtype: str
        """

        intervals = [False] * len(s)
        for i in range(0, len(s)):
            for word in dict:
                if s.startswith(word, i):
                    intervals[i:i + len(word)] = [True] * len(word)

        final_str = []
        bold_active = False
        for i, bold in enumerate(intervals):
            # start of bold
            if bold and not bold_active:
                final_str.append('<b>')
                bold_active = True
            # end of bold
            elif not bold and bold_active:
                final_str.append('</b>')
                bold_active = False
            final_str.append(s[i])

        if intervals[-1]:
            final_str.append('</b>')

        return ''.join(final_str)


obj = Solution()
print(obj.addBoldTag("abcxyz123", ["abc", "123"]))  # "<b>abc</b>xyz<b>123</b>"
print(obj.addBoldTag("aaabbcc", ["aaa","aab","bc"]))  # "<b>aaabbc</b>c"
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/616-add-bold-tag-in-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.