Is Bold Words in String easy or hard?

Bold Words in String is generally rated Medium. The challenge comes from combining efficient substring matching with correct interval merging. Once the matching ranges are marked correctly, generating the final tagged string becomes straightforward.

Bold Words in String Python/Java solution

Implementations typically build a Trie from the word list, scan the string to mark bold intervals, then construct the output with and tags. The same logic works in Python, Java, C++, and Go because it relies on basic Trie traversal and array marking.

How to solve Bold Words in String in O(n)?

Near-linear performance is achieved by building a Trie of all words and scanning the string once. At each position, traverse the Trie to find the longest matching prefix and update the farthest bold boundary. A boolean array or interval range records bold characters, and the final pass inserts tags around contiguous segments.

What is the best approach for Bold Words in String?

The most efficient approach builds a Trie from all dictionary words and scans the string from each index. Trie traversal finds all prefixes starting at that index without repeatedly comparing every word. This reduces redundant checks and runs in roughly O(n * L) time where n is the string length and L is the maximum word length.

Is Bold Words in String asked at Google/Amazon/Meta?

This style of problem appears in interviews that test string processing and dictionary matching. Variants involving substring highlighting, interval merging, or Trie-based matching have been reported in interviews at companies like Google, Amazon, and Meta.

What data structure is used in Bold Words in String?

Common solutions use a Trie for efficient prefix lookup along with an array or boolean marker to track bold ranges. The Trie stores dictionary words with shared prefixes, while the array helps merge overlapping or adjacent matches when constructing the final string.

What is the time complexity of Bold Words in String?

The optimal Trie-based solution runs in O(n * L) time, where n is the length of the string and L is the maximum length of any word in the dictionary. Building the Trie takes O(W) where W is the total number of characters across all words. Space complexity is O(W + n) for the Trie and the bold marker array.

Description Hints 1 Solution Video 12:34

758. Bold Words in String

Medium53.2% acceptance1 companyPremium elsewhere, free here

Given an array of keywords words and a string s, make all appearances of all keywords words[i] in s bold. Any letters between <b> and </b> tags become bold.

Return s after adding the bold tags. The returned string should use the least number of tags possible, and the tags should form a valid combination.

Example 1:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"
Explanation: Note that returning "a<b>a<b>b</b>c</b>d" would use more tags, so it is incorrect.

Example 2:

Input: words = ["ab","cb"], s = "aabcd"
Output: "a<b>ab</b>cd"

Constraints:

1 <= s.length <= 500
0 <= words.length <= 50
1 <= words[i].length <= 10
s and words[i] consist of lowercase English letters.

Note: This question is the same as 616. Add Bold Tag in String.

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

First, determine which letters are bold and store that information in mask[i] = if i-th character is bold. Then, insert the tags at the beginning and end of groups. The start of a group is if and only if (mask[i] and (i == 0 or not mask[i-1])), and the end of a group is similar.

12:34

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

["ab","bc"]
"aabcd"

Input

["ab","cb"]
"aabcd"

Your code is saved on this device.Solution