Skip to main content
Talentd

Add Bold Tag in String - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableStringTrie6 min readAsked at: Meta, Google, Gusto +1
Practice this problem

Problem Statement

You are given a string s and an array of strings words.

You should add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in words.

  • If two such substrings overlap, you should wrap them together with only one pair of closed bold-tag.
  • If two substrings wrapped by bold tags are consecutive, you should combine them.

Return s after adding the bold tags.

 

Example 1:

Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"
Explanation: The two strings of words are substrings of s as following: "abcxyz123".
We add <b> before each substring and </b> after each substring.

Example 2:

Input: s = "aaabbb", words = ["aa","b"]
Output: "<b>aaabbb</b>"
Explanation: 
"aa" appears as a substring two times: "aaabbb" and "aaabbb".
"b" appears as a substring three times: "aaabbb", "aaabbb", and "aaabbb".
We add <b> before each substring and </b> after each substring: "<b>a<b>a</b>a</b><b>b</b><b>b</b><b>b</b>".
Since the first two <b>'s overlap, we merge them: "<b>aaa</b><b>b</b><b>b</b><b>b</b>".
Since now the four <b>'s are consecutive, we merge them: "<b>aaabbb</b>".

 

Constraints:

  • 1 <= s.length <= 1000
  • 0 <= words.length <= 100
  • 1 <= words[i].length <= 1000
  • s and words[i] consist of English letters and digits.
  • All the values of words are unique.

 

Note: This question is the same as 758. Bold Words in String.

Approach Overview

Problem Overview: Given a string s and a list of dictionary words, wrap every substring in s that appears in the dictionary with <b> and </b>. Overlapping or adjacent matches must be merged into a single bold region.

Approach 1: Brute Force Matching + Interval Merge (O(n * k * L) time, O(n) space)

Scan the string from every index and check whether any dictionary word matches starting at that position using substring comparison. For each match, mark the covered indices in a boolean array or store intervals like [start, end]. After processing all matches, merge overlapping or adjacent intervals and construct the final string by inserting <b> and </b> around bold segments. This approach is straightforward and easy to implement, but repeated substring comparisons make it slower when the dictionary is large.

Approach 2: Boolean Marking with Longest Match Tracking (O(n * k * L) time, O(n) space)

Instead of storing intervals, maintain a boolean array bold[i] indicating whether character i should be bold. While iterating through s, check every dictionary word with a prefix comparison like s.startswith(word, i). Track the farthest index that should remain bold and mark characters up to that boundary. Finally, build the output string while opening a <b> tag when entering a bold region and closing it when leaving one. This method avoids explicit interval merging and is often the cleanest implementation.

Approach 3: Trie-Based String Matching (O(n * L) time, O(W * L) space)

Build a Trie from the dictionary words. Starting at each index in s, traverse the Trie while characters continue to match. Whenever a word end is reached, update the farthest bold boundary. This reduces redundant comparisons because common prefixes are shared in the Trie. The technique is common in string matching problems and works well when the dictionary contains many overlapping prefixes. Use an array or interval list to mark bold positions and generate the final string.

Recommended for interviews: The boolean marking approach is usually expected. It demonstrates clear reasoning about substring matching and interval merging while keeping the implementation simple. Mentioning a Trie optimization shows deeper understanding of scalable string matching techniques.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Matching + Interval MergeO(n * k * L)O(n)Good for understanding the problem and when dictionary size is small
Boolean Marking with Longest MatchO(n * k * L)O(n)Clean implementation for interviews; avoids explicit interval merging
Trie-Based String MatchingO(n * L)O(W * L)Best when dictionary has many words with shared prefixes

Video Solution

LeetCode 616. Add Bold Tag in String • Happy Coding • 4,474 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Add Bold Tag in String easy or hard?
Add Bold Tag in String is rated Medium difficulty. The main challenge is handling overlapping and adjacent matches correctly while constructing the final string. Once you recognize that all matches can be converted into merged intervals or a boolean marking array, the implementation becomes straightforward.
Add Bold Tag in String Python/Java solution
In Python or Java, iterate through the string and check each dictionary word using prefix matching such as startswith or substring comparison. Track the farthest bold boundary and mark characters in a boolean array. Finally, build the result by inserting <b> and </b> tags when transitioning between non-bold and bold regions.
How to solve Add Bold Tag in String in O(n)?
Near-linear performance can be achieved by building a Trie from all dictionary words and scanning the string while traversing the Trie for matching prefixes. Each character is processed while following possible matches up to the maximum word length L. This reduces redundant comparisons and results in O(n * L) time with O(W * L) space for the Trie structure.
What is the best approach for Add Bold Tag in String?
The boolean marking approach is typically the best balance of simplicity and efficiency. Iterate through the string, check if any dictionary word starts at each index, and track the farthest position that should remain bold. Mark characters in a boolean array and build the final string by opening and closing <b> tags when entering or leaving bold regions. Time complexity is O(n * k * L) where n is the string length, k is the number of words, and L is the maximum word length.
Is Add Bold Tag in String asked at Google/Amazon/Meta?
Add Bold Tag in String has appeared in interviews at companies that emphasize string manipulation and text processing, including Google and Facebook-style interview loops. The problem tests substring matching, interval merging, and careful string construction—skills frequently evaluated in mid-level algorithm interviews.
What data structure is used in Add Bold Tag in String?
Most solutions use arrays or interval lists to track which characters should be bold. A boolean array of length n is common for marking bold regions. For optimization, a Trie data structure can store dictionary words and enable efficient prefix-based string matching.
What is the time complexity of Add Bold Tag in String?
The common solution runs in O(n * k * L) time because for each position in the string you may check up to k words with length up to L. Space complexity is O(n) for the boolean array used to mark bold characters. A Trie-based optimization can reduce repeated prefix comparisons and achieve roughly O(n * L) matching time.

Ready to solve this problem?

Practice Add Bold Tag in String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Merge Intervals

Next

Tag Validator