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

Bold Words in String

Number: 760

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an array of keywords (words) and a string s, insert bold tags ( and ) around all occurrences of each keyword in s. Overlapping or consecutive occurrences should be merged to use the least number of tags possible, forming a valid tag structure.

Key Insights

  • Mark each character in s that is part of any keyword.
  • Use an auxiliary boolean array to track which indices require bold formatting.
  • Merge consecutive bold regions so that overlapping or adjacent keywords are wrapped in a single pair of bold tags.
  • Iterate over s once more to insert the tags based on the marked positions.

Space and Time Complexity

Time Complexity: O(n * m * k) worst-case, where n is the length of s, m is the number of words, and k is the average length of each word.
Space Complexity: O(n) due to the auxiliary boolean marker array and the output string.

Solution

The algorithm uses the following steps:

  1. Create a boolean array of the same length as s, initially set to False. This array will indicate which characters should be bolded.
  2. For every word in the keywords, find all occurrences in s and mark the corresponding indices in the boolean array to True.
  3. Traverse s and build the result string. Whenever a bold region is encountered (a sequence of indices marked True), wrap the sequence with and tags. Ensure to merge any contiguous bold regions to avoid extra tags.
  4. Return the constructed string with minimal bold tags.

This approach uses simple string matching, an auxiliary array for marking, and a linear pass to produce the final result.

Code Solutions

# Python solution for Bold Words in String

def addBoldTag(s, words):
    # Step 1: Initialize a boolean array to mark positions to be bolded
    n = len(s)
    bold = [False] * n

    # For each word in words, mark the matching indices as True
    for word in words:
        start = s.find(word)
        while start != -1:
            end = start + len(word)
            for i in range(start, end):
                bold[i] = True
            start = s.find(word, start + 1)
    
    # Step 2: Build the final string with bold tags inserted
    result = []
    i = 0
    while i < n:
        if not bold[i]:
            result.append(s[i])
            i += 1
        else:
            result.append("<b>")
            # Continue until the end of the bold region
            while i < n and bold[i]:
                result.append(s[i])
                i += 1
            result.append("</b>")
    return "".join(result)

# Example usage:
s = "aabcd"
words = ["ab", "bc"]
print(addBoldTag(s, words))  # Output: a<b>abc</b>d
← Back to All Questions