We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Add Bold Tag in String

Number: 616

Difficulty: Medium

Paid? Yes

Companies: Meta, Gusto, Microsoft, Google

Problem Description

Given a string s and an array of strings words, add a pair of bold tags ( and ) to wrap all substrings in s that match any word in words. If the intervals of matching substrings overlap or are consecutive, they should be merged into a single continuous bold section.

Key Insights

  • We need to identify every occurrence of each word in s.
  • Overlapping or consecutive intervals should be merged to form one continuous bold region.
  • Use an auxiliary data structure (e.g., a boolean array) to mark positions that should be bolded.
  • Once the positions are marked, build the final string by inserting bold tags at the appropriate boundaries.

Space and Time Complexity

Time Complexity: O(n * m * k) where n is the length of s, m is the number of words, and k is the average length of the words (due to substring matching). Space Complexity: O(n) for the auxiliary boolean array used to mark bold positions.

Solution

The solution involves two main steps:

  1. Identify and mark the indices in the string s that are part of any matching word. We do this by iterating over each word and marking every occurrence’s start and end in a boolean array.
  2. Construct the final string by traversing the boolean array. When encountering a segment of consecutive true values, wrap that segment with and tags.

The key idea is to merge intervals by marking every index that should be bold and then using a single pass to insert tags only when transitioning from non-bold to bold and vice versa.

Code Solutions

# Python Code Solution
def addBoldTag(s, words):
    n = len(s)
    # Mark positions to be bolded
    bold = [False] * n
    # Iterate each word and mark its occurrences
    for word in words:
        start = s.find(word)
        while start != -1:
            for i in range(start, start + len(word)):
                bold[i] = True
            start = s.find(word, start + 1)
    
    # Build the final result with bold tags
    result = []
    i = 0
    while i < n:
        if not bold[i]:
            result.append(s[i])
            i += 1
        else:
            result.append("<b>")
            while i < n and bold[i]:
                result.append(s[i])
                i += 1
            result.append("</b>")
    return "".join(result)

# Example usage:
# s = "abcxyz123"
# words = ["abc", "123"]
# print(addBoldTag(s, words))  # "<b>abc</b>xyz<b>123</b>"
    
# Line-by-line:
# 1. Initialize an array "bold" of length n to track which characters need bold formatting.
# 2. For each word, use string.find to locate every occurrence and mark the corresponding indices.
# 3. Traverse the string s. If the current character is marked bold and it is the start of a bold segment,
#    insert the opening tag before appending characters until the end of that bold segment.
# 4. Append the closing tag after the bold segment and continue the process.
← Back to All Questions