Domain 1EasyCORE

Bold Words in String

The problem requires us to make all appearances of given keywords in a string bold by wrapping them with `<b>` and `</b>` tags. The goal is to use the least number of tags possible while ensuring that the tags form a valid combination.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

758. Bold Words in String

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 47.5%


Problem Breakdown

The problem requires us to make all appearances of given keywords in a string bold by wrapping them with <b> and </b> tags. The goal is to use the least number of tags possible while ensuring that the tags form a valid combination.

Inputs:

  • A list of keywords words where each keyword is a string.
  • A string S which contains lowercase letters.

Outputs:

  • A modified version of S with all occurrences of any keyword in words bolded.

Implicit Constraints or Tricky Edge Cases:

  • If words is empty, the original string S should be returned unchanged.
  • If S is empty, the result should also be an empty string.
  • Keywords can overlap, and we need to ensure that overlapping keywords are handled correctly by using the minimum number of tags.

Intuition

A brute-force approach would involve checking every substring of S against each keyword in words and marking the positions where a keyword appears. This would result in a high time complexity due to the nested loops over all substrings and keywords.

The key insight is to use an array to mark the start and end positions of bold tags. By iterating through S, we can identify the ranges where any keyword starts or ends, and then merge these ranges to minimize the number of tags used. This approach reduces the complexity by avoiding unnecessary nested loops.

Approach

  1. Initialize a Marking Array: Create an array mark of length equal to the length of S. Each element in this array will be set to 1 if it is part of any keyword, otherwise 0.
  2. Mark Positions: For each word in words, iterate through S and mark the positions where the word starts as 1 in the mark array.
  3. Merge Ranges: Iterate through the mark array to identify contiguous ranges of 1s. These ranges represent the substrings that need to be bolded.
  4. Construct Result String: Build the result string by appending characters from S and adding <b> and </b> tags where necessary based on the identified ranges.

Complexity Analysis

  • Time Complexity: O(n * m), where n is the length of S and m is the total number of characters in all keywords combined. This is because we iterate through S for each keyword.
  • Space Complexity: O(n) for storing the mark array and the result string.

Solution

def boldWords(words, S):
    n = len(S)
    mark = [0] * n
    
    # Mark positions in 'mark' where keywords appear
    for word in words:
        start = 0
        while start < n:
            pos = S.find(word, start)
            if pos == -1:
                break
            for i in range(pos, pos + len(word)):
                mark[i] = 1
            start = pos + 1
    
    # Construct the result string with bold tags
    ans = []
    i = 0
    while i < n:
        if mark[i] == 1:
            ans.append("<b>")
            while i < n and mark[i] == 1:
                ans.append(S[i])
                i += 1
            ans.append("</b>")
        else:
            ans.append(S[i])
            i += 1
    
    return ''.join(ans)

Edge Cases Handled

  • Empty words: The function returns the original string S unchanged.
  • Empty S: The function returns an empty string.
  • Overlapping Keywords: The function correctly merges overlapping ranges to use the minimum number of tags.

The solution provided is correct, efficient, and clear. It handles all edge cases as described in the problem breakdown.