Problem Description

You are given a string s and an array of strings words. Your task is to add HTML bold tags (<b> and </b>) around substrings in s that match any word in the words array.

The key rules for adding bold tags are:

1. Find all matching substrings: Any substring of s that exactly matches a word from words should be wrapped with bold tags.

2. Merge overlapping regions: If two substrings that need to be bolded overlap (share at least one character), they should be wrapped together with a single pair of bold tags instead of having nested or overlapping tags.

3. Merge consecutive regions: If two bold regions are adjacent (the end of one bold region is immediately followed by the start of another), they should be combined into one continuous bold region.

For example:

• If s = "abcxyz" and words = ["abc", "xyz"], the result would be "<b>abcxyz</b>" because the two words are consecutive.
• If s = "aaabbcc" and words = ["aaa", "aab", "bc"], the result would be "<b>aaabbc</b>c" because "aaa" and "aab" overlap (sharing "aa"), and "aab" and "bc" overlap (sharing "b"), creating one continuous bold region.

The solution uses a Trie data structure to efficiently find all matching substrings in s. It first identifies all intervals that need to be bolded, then merges overlapping or consecutive intervals, and finally constructs the result string with the appropriate bold tags inserted.

Intuition

The core challenge is efficiently finding all occurrences of words from the words array within the string s, then merging overlapping or adjacent regions.

A naive approach would be to check each word against every position in s, but this becomes inefficient when we have many words or long strings. Instead, we can think of this problem in reverse: for each position in s, we want to find all words that start at that position.

This naturally leads us to use a Trie (prefix tree) structure. Why? Because a Trie allows us to simultaneously check for multiple words while traversing through the string character by character. As we move through s starting from each position, we can traverse the Trie and identify all valid words that begin at that position.

The process breaks down into three logical steps:

1. Build a Trie from all words to enable efficient multi-pattern matching.

2. Find all intervals that need to be bolded. For each starting position i in s, we traverse the Trie to find all words that match substrings starting at i. Each match gives us an interval [start, end] that needs bold tags.

3. Merge intervals that overlap or are consecutive. This is a classic interval merging problem - if the end of one interval touches or overlaps with the start of the next interval (i.e., end + 1 >= next_start), we merge them into a single interval. This ensures we don't have nested tags or immediately adjacent bold regions.

The beauty of this approach is that the Trie allows us to find all matching words in a single pass from each position, making the algorithm efficient even with many words to search for. The interval merging step then cleanly handles the requirement to combine overlapping and adjacent bold regions.

Learn more about Trie patterns.

Solution Approach

The implementation consists of three main components: building a Trie, finding all matching intervals, and merging those intervals.

1. Building the Trie Structure

The Trie class is implemented with:

• children: An array of size 128 to accommodate all ASCII characters (using ord(c) as the index)
• is_end: A boolean flag marking if a word ends at this node

def insert(self, word):
    node = self
    for c in word:
        idx = ord(c)
        if node.children[idx] is None:
            node.children[idx] = [Trie](/problems/trie_intro)()
        node = node.children[idx]
    node.is_end = True

All words from the words array are inserted into the Trie for efficient pattern matching.

2. Finding All Matching Intervals

For each position i in string s, we traverse the Trie to find all words that start at position i:

for i in range(n):
    node = [trie](/problems/trie_intro)
    for j in range(i, n):
        idx = ord(s[j])
        if node.children[idx] is None:
            break
        node = node.children[idx]
        if node.is_end:
            pairs.append([i, j])

When we find a complete word (marked by is_end = True), we record the interval [i, j] where i is the start index and j is the end index of the matching substring.

3. Merging Overlapping and Adjacent Intervals

After collecting all intervals, we merge those that overlap or are consecutive:

st, ed = pairs[0]
t = []
for a, b in pairs[1:]:
    if ed + 1 < a:  # No overlap or adjacency
        t.append([st, ed])
        st, ed = a, b
    else:  # Overlap or adjacent
        ed = max(ed, b)
t.append([st, ed])

The merging logic checks if ed + 1 < a, which means there's a gap between intervals. If true, we save the current interval and start a new one. Otherwise, we extend the current interval by updating ed = max(ed, b).

4. Constructing the Final String

Finally, we build the result string by iterating through s and the merged intervals simultaneously:

ans = []
i = j = 0
while i < n:
    if j == len(t):
        ans.append(s[i:])
        break
    st, ed = t[j]
    if i < st:
        ans.append(s[i:st])  # Add non-bold text
    ans.append('<b>')
    ans.append(s[st : ed + 1])  # Add bold text
    ans.append('</b>')
    j += 1
    i = ed + 1

The algorithm maintains two pointers: i for the current position in string s, and j for the current interval in the merged list. It adds non-bold text between intervals and wraps the intervals with <b> tags.

The time complexity is O(n * m + k) where n is the length of s, m is the average length of words, and k is the total number of matching intervals. The space complexity is O(T + k) where T is the size of the Trie.

Example Walkthrough

Let's walk through a concrete example to see how the solution works step by step.

Given:

• s = "aaabbcc"
• words = ["aaa", "aab", "bc"]

Step 1: Build the Trie

We insert all words into the Trie structure:

Root
├── a
│   └── a
│       ├── a (is_end = True)  // "aaa"
│       └── b (is_end = True)  // "aab"
└── b
    └── c (is_end = True)      // "bc"

Step 2: Find All Matching Intervals

Now we scan through each position in s = "aaabbcc" and find matches:

• Position 0 ("aaabbcc"):

  • Follow path a→a→a in Trie → Found "aaa" at [0,2]
  • Follow path a→a→b in Trie → Found "aab" at [0,3]

• Position 1 ("aabbcc"):

  • Follow path a→a→b in Trie → Found "aab" at [1,4]

• Position 2 ("abbcc"):

  • Follow path a→b in Trie → No match (path doesn't exist)

• Position 3 ("bbcc"):

  • Follow path b→b in Trie → No match (path doesn't exist)

• Position 4 ("bcc"):

  • Follow path b→c in Trie → Found "bc" at [4,5]

• Position 5 ("cc"):

  • Follow path c in Trie → No match (no child 'c' from root)

• Position 6 ("c"):

  • Follow path c in Trie → No match (no child 'c' from root)

Collected intervals: [[0,2], [0,3], [1,4], [4,5]]

Step 3: Merge Overlapping/Adjacent Intervals

Sort intervals by start position (already sorted): [[0,2], [0,3], [1,4], [4,5]]

Merging process:

1. Start with [0,2]
2. Check [0,3]: Since 2+1 ≥ 0 (overlapping), merge to [0,3]
3. Check [1,4]: Since 3+1 ≥ 1 (overlapping), merge to [0,4]
4. Check [4,5]: Since 4+1 ≥ 4 (adjacent), merge to [0,5]

Merged intervals: [[0,5]]

Step 4: Construct Final String

With merged interval [0,5] and s = "aaabbcc":

• Position 0: Start of interval [0,5]
  • Add <b>
  • Add substring from index 0 to 5: "aaabbc"
  • Add </b>
• Position 6: After interval ends
  • Add remaining string: "c"

Final Result: "<b>aaabbc</b>c"

The overlapping matches "aaa" (positions 0-2), "aab" (positions 0-3 and 1-4), and "bc" (positions 4-5) all merge into one continuous bold region because they share characters or are adjacent, resulting in a single pair of bold tags around "aaabbc".

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² * m + n * k)

• Building the Trie: O(m * L) where m is the number of words and L is the average length of words
• Finding all matching intervals: O(n²) where n is the length of string s
  • For each starting position i (n positions), we potentially check up to n - i characters
  • In worst case, this gives us O(n²) operations
• Merging intervals: O(k log k) where k is the number of intervals found (implicit sorting when processing pairs)
  • Although not explicitly sorted in this code, the pairs are processed in order due to how they're generated
  • Merging itself takes O(k) time
• Building the final string: O(n) to construct the result

Overall: O(m * L + n² + k log k + n) which simplifies to O(n² + m * L) as n² typically dominates

Space Complexity: O(m * L * 128 + k + n)

• Trie storage: O(m * L * 128) where each Trie node has an array of 128 children
  • In worst case, we store m * L nodes, each with 128 pointers
• Intervals storage: O(k) where k is the number of matching intervals found
• Result string construction: O(n) for the answer list before joining
• Call stack for Trie operations: O(L) maximum depth

Overall: O(m * L * 128 + k + n) which is dominated by the Trie structure's space requirement of O(m * L * 128)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Interval Merging Logic

The Pitfall: One of the most common mistakes is incorrectly determining when intervals should be merged. Developers often forget to handle adjacent intervals (where one interval ends exactly before another begins) or use the wrong comparison operator.

Incorrect Implementation:

# Wrong: Only merges overlapping intervals, misses adjacent ones
if end < curr_start:  # Should be end + 1 < curr_start
    merged_intervals.append([start, end])
    start, end = curr_start, curr_end
else:
    end = max(end, curr_end)

Why It's Wrong: Using end < curr_start only merges intervals that overlap. It misses the case where intervals are adjacent (touching but not overlapping). For example, if we have intervals [0, 2] and [3, 5] representing bold regions for indices 0-2 and 3-5, they should be merged into [0, 5] to create one continuous bold tag <b>...</b> instead of two separate ones <b>...</b><b>...</b>.

Correct Implementation:

# Correct: Merges both overlapping AND adjacent intervals
if end + 1 < curr_start:  # Gap exists between intervals
    merged_intervals.append([start, end])
    start, end = curr_start, curr_end
else:
    end = max(end, curr_end)

2. Not Sorting Intervals Before Merging

The Pitfall: The code assumes intervals are already sorted by start position, but depending on how intervals are collected, they might not be in order.

Problem Scenario:

# If intervals are collected in this order (not sorted):
intervals = [[3, 5], [0, 2], [4, 6]]
# Merging without sorting will produce incorrect results

Solution: Always sort intervals before merging:

# Sort intervals by start position, then by end position
intervals.sort()  # Python's sort handles tuples/lists correctly

3. Off-by-One Errors in String Slicing

The Pitfall: Confusion between inclusive and exclusive indices when building the result string.

Incorrect:

# Wrong: Forgets that interval_end is inclusive
result.append(s[interval_start:interval_end])  # Missing the last character

Correct:

# Correct: Include the character at interval_end
result.append(s[interval_start:interval_end + 1])

4. Handling Empty Input Cases

The Pitfall: Not properly handling edge cases like empty strings or empty word lists.

Solution: Add validation at the beginning:

if not s or not words:
    return s

5. Trie Size Assumption

The Pitfall: Using a fixed-size array of 128 for ASCII characters might fail for Unicode strings or special characters beyond standard ASCII range.

Better Approach for Unicode:

class Trie:
    def __init__(self):
        # Use dictionary instead of fixed array for Unicode support
        self.children = {}
        self.is_end = False
  
    def insert(self, word):
        node = self
        for char in word:
            if char not in node.children:
                node.children[char] = Trie()
            node = node.children[char]
        node.is_end = True

Complete Corrected Solution with Safeguards:

class Solution:
    def addBoldTag(self, s: str, words: List[str]) -> str:
        # Handle edge cases
        if not s or not words:
            return s
      
        # Build trie and find intervals (same as before)
        trie = Trie()
        for word in words:
            trie.insert(word)
      
        n = len(s)
        intervals = []
      
        for i in range(n):
            node = trie
            for j in range(i, n):
                index = ord(s[j])
                if node.children[index] is None:
                    break
                node = node.children[index]
                if node.is_end:
                    intervals.append([i, j])
      
        if not intervals:
            return s
      
        # IMPORTANT: Sort intervals before merging
        intervals.sort()
      
        # Merge with correct adjacency check
        merged = []
        start, end = intervals[0]
      
        for curr_start, curr_end in intervals[1:]:
            if end + 1 < curr_start:  # Correct adjacency check
                merged.append([start, end])
                start, end = curr_start, curr_end
            else:
                end = max(end, curr_end)
        merged.append([start, end])
      
        # Build result with correct string slicing
        result = []
        i = 0
        for start, end in merged:
            if i < start:
                result.append(s[i:start])
            result.append('<b>')
            result.append(s[start:end + 1])  # +1 for inclusive end
            result.append('</b>')
            i = end + 1
      
        if i < n:
            result.append(s[i:])
      
        return ''.join(result)