Problem Description

You are given an array of keyword strings words and a string s. Your task is to make all occurrences of the keywords in s bold by wrapping them with HTML bold tags <b> and </b>.

The key requirements are:

1. Find all occurrences of each keyword from words that appear in string s
2. Wrap these occurrences with <b> and </b> tags to make them bold
3. Use the minimum number of tags possible - if keywords overlap or are adjacent, they should share the same pair of bold tags
4. The tags must form valid HTML combinations

For example, if you have overlapping keywords that both need to be bolded, instead of creating nested or separate tags like <b>key</b><b>word</b>, you should merge them into a single bolded section <b>keyword</b>.

The algorithm uses a Trie data structure to efficiently find all keyword matches in the string. It:

• Builds a Trie from all the keywords
• Finds all matching intervals [start, end] where keywords appear in s
• Merges overlapping or adjacent intervals to minimize the number of bold tags
• Constructs the final string by inserting <b> and </b> tags at the appropriate positions

The solution ensures that overlapping or consecutive bold sections are merged into single continuous bold regions, achieving the requirement of using the least number of tags possible.

Intuition

The core challenge is efficiently finding all occurrences of multiple keywords in a string and then merging overlapping regions. Let's think about how to approach this step by step.

First, we need to find all keyword matches. A naive approach would be to check each keyword at every position in the string, but this would be inefficient with time complexity O(n * m * k) where n is the length of string, m is the number of keywords, and k is the average keyword length.

This is where the Trie comes in. By building a Trie from all keywords, we can simultaneously check for all possible keyword matches starting from any position in just one traversal. At each position i in the string, we traverse the Trie character by character. Whenever we reach a node marked as is_end, we know we've found a complete keyword match from position i to the current position.

Once we have all the matching intervals, we face the second challenge: merging overlapping or adjacent intervals. Why do we need this? Consider the string "aaabbcc" with keywords ["aaa", "aab", "bc"]. Without merging, we might get <b>aaa</b><b>b</b><b>bc</b>c, but the optimal result should be <b>aaabbc</b>c with just one pair of tags.

The merging logic follows a simple rule: if two intervals overlap or are adjacent (meaning the end of one interval is at position j and the start of the next is at position j+1 or less), they should be combined into a single interval. We sort the intervals by start position and then iterate through them, extending the current interval when overlaps occur or starting a new interval when there's a gap.

Finally, we reconstruct the string by iterating through the original string and the merged intervals simultaneously, inserting bold tags at the appropriate positions. This ensures we maintain the original string content while adding the minimum number of tags needed.

The beauty of this approach is that it separates the problem into three independent, manageable steps: finding matches efficiently with a Trie, merging intervals to minimize tags, and reconstructing the final string with proper tag placement.

Learn more about Trie patterns.

Solution Approach

The solution implements a three-phase approach: building a Trie for efficient pattern matching, finding all keyword occurrences, and merging overlapping intervals.

Phase 1: Building the Trie

We create a Trie class with 128 children (to handle ASCII characters) and an is_end flag to mark complete words. The insert method adds each keyword character by character:

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

Phase 2: Finding All Keyword Matches

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

pairs = []
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  # No more matches possible
        node = node.children[idx]
        if node.is_end:
            pairs.append([i, j])  # Found keyword from i to j

This generates intervals [start, end] for each keyword occurrence. For example, if "abc" appears at position 2, we get [2, 4].

Phase 3: Merging Overlapping Intervals

We merge intervals that overlap or are adjacent to minimize bold tags:

st, ed = pairs[0]
t = []
for a, b in pairs[1:]:
    if ed + 1 < a:  # Gap between intervals
        t.append([st, ed])
        st, ed = a, b
    else:  # Overlapping or adjacent
        ed = max(ed, b)  # Extend current interval
t.append([st, ed])

The condition ed + 1 < a checks if there's a gap. If ed = 3 and a = 4, they're adjacent (positions 3 and 4), so we merge them. If a = 5, there's a gap at position 4, so we start a new interval.

Phase 4: Reconstructing the String

Finally, we build the result string by iterating through both the original string and merged intervals:

ans = []
i = j = 0
while i < n:
    if j == len(t):
        ans.append(s[i:])  # Append remaining string
        break
    st, ed = t[j]
    if i < st:
        ans.append(s[i:st])  # Add non-bold portion
    ans.append('<b>')
    ans.append(s[st : ed + 1])  # Add bold portion
    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 portions between intervals and wraps bold portions with tags.

Time Complexity: O(n * m) where n is the length of string s and m is the maximum length of any keyword, as we check for keywords starting at each position.

Space Complexity: O(k * m) for the Trie where k is the number of keywords and m is their average length, plus O(n) for storing intervals.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Input:

• words = ["ab", "bc"]
• s = "aabcd"

Step 1: Build the Trie

We construct a Trie from the keywords:

     root
     / \
    a   b
    |   |
    b*  c*

The asterisk (*) indicates is_end = True, marking complete words.

Step 2: Find All Keyword Matches

We check each position in s = "aabcd":

• Position 0 ('a'):

  • Follow 'a' in Trie → found
  • Follow 'a' → 'b' → found "ab" at [0, 1] ✓
  • No more matches from position 0

• Position 1 ('a'):

  • Follow 'a' in Trie → found
  • Follow 'a' → 'b' → found "ab" at [1, 2] ✓
  • No more matches from position 1

• Position 2 ('b'):

  • Follow 'b' in Trie → found
  • Follow 'b' → 'c' → found "bc" at [2, 3] ✓
  • No more matches from position 2

• Position 3 ('c'):

  • Follow 'c' in Trie → not found
  • No matches from position 3

• Position 4 ('d'):

  • Follow 'd' in Trie → not found
  • No matches from position 4

Found intervals: [[0, 1], [1, 2], [2, 3]]

Step 3: Merge Overlapping/Adjacent Intervals

Sort intervals (already sorted): [[0, 1], [1, 2], [2, 3]]

Merging process:

• Start with [0, 1]
• Check [1, 2]: Since 1 + 1 = 2 ≥ 1 (adjacent), merge → [0, 2]
• Check [2, 3]: Since 2 + 1 = 3 ≥ 2 (adjacent), merge → [0, 3]

Merged intervals: [[0, 3]]

Step 4: Reconstruct String with Bold Tags

Original string: "aabcd" Merged intervals: [[0, 3]]

Building the result:

• i = 0, j = 0
• Interval [0, 3]: Add <b> + s[0:4] + </b> → <b>aabc</b>
• i = 4, j = 1 (no more intervals)
• Add remaining s[4:] → "d"

Final Result: "<b>aabc</b>d"

The keywords "ab" (appearing twice) and "bc" all overlap or are adjacent, so they're merged into one continuous bold section, using just one pair of bold tags instead of three.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * k + n^2)

• Building the Trie: O(m * k) where m is the number of words and k is the average length of each word. Each word requires traversing and potentially creating nodes for each character.

• Finding all matching intervals: O(n^2) where n is the length of string s. For each starting position i in the string (n positions), we potentially check up to n - i characters to find all words starting at position i. In the worst case, this gives us O(n^2) operations.

• Merging intervals: O(p) where p is the number of matching pairs found. In the worst case, p could be O(n^2) if many overlapping words are found.

• Building the final string: O(n) as we traverse through the string once to construct the result.

Overall time complexity is dominated by O(m * k + n^2).

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

• Trie storage: O(m * k * 128) in the worst case. Each Trie node has an array of 128 children (for ASCII characters). With m words of average length k, we could have up to m * k nodes, each consuming O(128) space.

• Pairs list: O(p) where p is the number of matching intervals, which could be O(n^2) in the worst case.

• Merged intervals list t: O(n) in the worst case when all intervals are disjoint.

• Result string construction: O(n) for the answer list and final string.

The space complexity is dominated by the Trie structure, giving us O(m * k * 128 + n).

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

Common Pitfalls

1. Incorrect Interval Merging Logic

The most common pitfall is incorrectly determining when intervals should be merged. Many developers make the mistake of only checking for overlapping intervals (end >= curr_start) but forget to handle adjacent intervals.

Incorrect approach:

# This only merges overlapping intervals, not adjacent ones
if end >= curr_start:
    end = max(end, curr_end)
else:
    merged_intervals.append([start, end])
    start, end = curr_start, curr_end

Why it's wrong: If you have the word "abc" at position [0,2] and "def" at position [3,5], and both are keywords, the output would be <b>abc</b><b>def</b> instead of the desired <b>abcdef</b>.

Correct approach:

# Check if there's a gap between intervals
if end + 1 < curr_start:  # Gap exists when end+1 < curr_start
    merged_intervals.append([start, end])
    start, end = curr_start, curr_end
else:  # Adjacent or overlapping
    end = max(end, curr_end)

2. Off-by-One Errors in String Slicing

Another frequent mistake occurs when reconstructing the final string with bold tags. The intervals store inclusive end positions, but Python string slicing uses exclusive end indices.

Incorrect approach:

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

Correct approach:

# Add 1 to interval_end since it's inclusive
result.append(s[interval_start:interval_end + 1])

3. Not Handling Empty or Edge Cases

Failing to check for empty matched intervals before attempting to merge them causes index errors.

Incorrect approach:

# Directly accessing first element without checking
start, end = matched_intervals[0]  # IndexError if matched_intervals is empty

Correct approach:

# Check if any matches were found
if not matched_intervals:
    return s

start, end = matched_intervals[0]

4. Inefficient Trie Implementation for ASCII Characters

Using a dictionary for Trie children when dealing with ASCII characters adds unnecessary overhead and complexity.

Less efficient approach:

class Trie:
    def __init__(self):
        self.children = {}  # Dictionary approach
        self.is_end = False
  
    def insert(self, word):
        node = self
        for c in word:
            if c not in node.children:
                node.children[c] = Trie()
            node = node.children[c]

More efficient approach:

class Trie:
    def __init__(self):
        self.children = [None] * 128  # Array for ASCII characters
        self.is_end = False

5. Incorrect Pointer Updates After Adding Bold Tags

When reconstructing the string, updating the string index incorrectly can lead to duplicated or skipped characters.

Incorrect approach:

# Using interval_end instead of interval_end + 1
string_index = interval_end  # This would duplicate the character at interval_end

Correct approach:

# Move past the last character of the current bold section
string_index = interval_end + 1

Prevention Strategy

To avoid these pitfalls:

1. Draw out examples with adjacent intervals like [0,2] and [3,5] to verify merge logic
2. Test with edge cases including empty words list, no matches, and single character strings
3. Use clear variable names like inclusive_end to remind yourself about index boundaries
4. Add assertions during development to catch off-by-one errors early
5. Walk through the algorithm with a simple example like words = ["ab", "bc"] and s = "abc" to ensure correct merging