Jobs

Interviews

Discussions

Bold Words in String

Medium

Asked by:

42 views

Topics:

StringsArrays

Given an array of keywords words and a string s, make all appearances of the keywords (each as a substring) in s bold. Any letters are covered by more than one keyword should be covered by only one pair of <b> and </b> tags. Return s after adding the bold tags.

Example 1:

Input: words = ["abc","bcd","abcd"], s = "abcxyzzabcdabcdabc"
Output: "<b>abc</b>xyzz<b>abcd</b><b>abcdabc</b>"

Example 2:

Input: words = ["ab","cb"], s = "abcxyz123"
Output: "<b>ab</b>cxyz123"

Constraints:

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

Try coding it in LeetCode

Bold Words in String

Medium

Asked by:

42 views

Topics:

StringsArrays

Example 1:

Input: words = ["abc","bcd","abcd"], s = "abcxyzzabcdabcdabc"
Output: "<b>abc</b>xyzz<b>abcd</b><b>abcdabc</b>"

Example 2:

Input: words = ["ab","cb"], s = "abcxyz123"
Output: "<b>ab</b>cxyz123"

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the words in the `words` array contain overlapping characters, and if so, how should the bolding be handled in those cases?
What is the expected behavior if the same word appears multiple times in the string `s`? Should all occurrences be bolded?
Can the input string `s` or any of the words in the `words` array be empty strings or null?
What is the maximum length of the input string `s` and the `words` array, and what is the maximum length of any individual word in `words`?
If no words from the `words` array are found in the string `s`, should I return the original string `s` without any bold tags?

Brute Force Solution

Approach

The brute force approach involves checking every possible combination to identify which parts of a string need to be bolded. We go through the string and each individual word to see if that word exists in the string. If we find the word, we highlight those parts to be bolded.

Here's how the algorithm would work step-by-step:

For every starting position in the main string, consider it as the beginning of a potential bolded segment.
Check if any of the words we want to bold start at this position in the main string.
If a word does start at this position, mark the corresponding section of the main string as needing to be bolded.
Repeat the process, checking every possible starting position in the main string.
Once we have gone through the entire main string and checked all possible words, we know exactly which parts need to be bolded.

Code Implementation

def bold_words_brute_force(string, words):
    string_length = len(string)
    bold_mask = [False] * string_length

    # Iterate through each starting position in the string
    for starting_position in range(string_length):
        # Check each word in our dictionary
        for word in words:
            if string[starting_position:].startswith(word):

                # Mark the substring to be bolded
                for i in range(len(word)):
                    bold_mask[starting_position + i] = True

    result = ""
    bold = False
    for i in range(string_length):
        if bold_mask[i] and not bold:
            result += "<b>"
            bold = True
        elif not bold_mask[i] and bold:

            # Close the bold tag when needed
            result += "</b>"
            bold = False
        result += string[i]

    if bold:
        result += "</b>"

    return result

Big(O) Analysis

Time Complexity

O(n*m*k) – Let n be the length of the input string, m be the number of words in the words array, and k be the maximum length of a word in the words array. The outer loop iterates through each of the n characters in the string. For each character, we iterate through the m words in the words array. For each word, we perform a substring comparison of up to k characters to see if the word starts at the current position in the string. Therefore, the overall time complexity is O(n*m*k).

Space Complexity

O(N) – The brute force approach requires marking sections of the main string as needing to be bolded. This can be done using an auxiliary boolean array of size N, where N is the length of the main string. Each element in the array corresponds to a character in the string, indicating whether it should be bolded or not. Therefore, the space complexity is directly proportional to the length of the string.

Optimal Solution

Approach

The goal is to highlight specific words within a larger string by wrapping them in bold tags. The clever approach is to first mark the start and end positions where bolding should occur and then construct the final string based on these marked positions. This avoids repeatedly searching for the words.

Here's how the algorithm would work step-by-step:

First, imagine marking positions in the main string that should be bolded. Think of it like using a highlighter to mark the start and end of each word to be bolded.
For each of the words we want to bold, find all places where that word shows up in the main string.
For each occurrence, mark the start and end positions of that word in the main string as needing to be bolded. If any bold sections overlap, merge them into a single, larger bold section.
Now, go through the main string, and whenever you encounter a marked start position, insert a bold start tag. When you encounter a marked end position, insert a bold end tag.
Finally, combine the original characters of the main string and the bold tags to construct the final output string.

Code Implementation

def bold_words_in_string(string_to_bold, words_to_bold):
    string_length = len(string_to_bold)
    bold_marker = [False] * string_length

    for word in words_to_bold:
        for index in range(string_length - len(word) + 1):
            if string_to_bold[index:index + len(word)] == word:
                # Mark the positions to be bolded
                for marker_index in range(index, index + len(word)): 
                    bold_marker[marker_index] = True

    merged_markers = []
    start_index = -1

    for index, should_bold in enumerate(bold_marker):
        if should_bold and start_index == -1:
            start_index = index
        elif not should_bold and start_index != -1:
            merged_markers.append((start_index, index))
            start_index = -1

    if start_index != -1:
        merged_markers.append((start_index, string_length))

    result = ""
    marker_index = 0

    for index in range(string_length):
        if marker_index < len(merged_markers) and index == merged_markers[marker_index][0]:
            # Insert bold tag at the start
            result += "<b>"
        result += string_to_bold[index]
        if marker_index < len(merged_markers) and index == merged_markers[marker_index][1] - 1:
            # Insert closing bold tag at the end
            result += "</b>"
            marker_index += 1

    return result

Big(O) Analysis

Time Complexity

O(n*m*k) – Let n be the length of the input string S, m be the number of words in the input word list words, and k be the maximum length of a word in words. First, we iterate through each word in words (m). For each word, we search for all occurrences of that word in S. Finding each occurrence of a word of length k in string S can take O(n*k) time using string searching methods (like naive string matching). Since we do this for each of the m words, the overall time complexity becomes O(n*m*k). Building the final string with bold tags involves another iteration through the string S which is O(n), but this is dominated by O(n*m*k).

Space Complexity

O(N) – The algorithm uses a boolean array, 'bold', of size N, where N is the length of the input string, to mark the start and end positions of the words to be bolded. While merging overlapping bold sections, this array tracks the intervals. The final output string construction potentially requires creating a new string of size proportional to the original string length, also contributing O(N) space. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
words array is empty	Return the original string since there are no words to bold.
s is empty	Return an empty string, as there's nothing to bold in an empty string.
s is null or words is null	Throw IllegalArgumentException to indicate invalid input.
words contains an empty string	Treat the empty string as matching anything, resulting in the entire string 's' being bolded.
words contains duplicates	The algorithm should still function correctly, potentially increasing the number of bolded sections if overlaps exist.
words contains overlapping matches in s	The solution must correctly merge overlapping bolded sections into single, larger bolded sections.
s is very long and words is very large, potentially exceeding memory limits or causing a timeout.	The chosen algorithm (e.g., using boolean array marking) must have reasonable time and space complexity (ideally O(n*m) where n is len(s) and m is the total length of all words).
No word in 'words' exists in 's'	Return the original string 's' unmodified, as there are no words to bold.

words array is empty

How to Handle:

Return the original string since there are no words to bold.

s is empty

How to Handle:

Return an empty string, as there's nothing to bold in an empty string.

s is null or words is null

How to Handle:

Throw IllegalArgumentException to indicate invalid input.

words contains an empty string

How to Handle:

Treat the empty string as matching anything, resulting in the entire string 's' being bolded.

words contains duplicates

How to Handle:

The algorithm should still function correctly, potentially increasing the number of bolded sections if overlaps exist.

words contains overlapping matches in s

How to Handle:

The solution must correctly merge overlapping bolded sections into single, larger bolded sections.

s is very long and words is very large, potentially exceeding memory limits or causing a timeout.

How to Handle:

The chosen algorithm (e.g., using boolean array marking) must have reasonable time and space complexity (ideally O(n*m) where n is len(s) and m is the total length of all words).

No word in 'words' exists in 's'

How to Handle:

Return the original string 's' unmodified, as there are no words to bold.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the words in the `words` array contain overlapping characters, and if so, how should the bolding be handled in those cases?
What is the expected behavior if the same word appears multiple times in the string `s`? Should all occurrences be bolded?
Can the input string `s` or any of the words in the `words` array be empty strings or null?
What is the maximum length of the input string `s` and the `words` array, and what is the maximum length of any individual word in `words`?
If no words from the `words` array are found in the string `s`, should I return the original string `s` without any bold tags?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

For every starting position in the main string, consider it as the beginning of a potential bolded segment.
Check if any of the words we want to bold start at this position in the main string.
If a word does start at this position, mark the corresponding section of the main string as needing to be bolded.
Repeat the process, checking every possible starting position in the main string.
Once we have gone through the entire main string and checked all possible words, we know exactly which parts need to be bolded.

Code Implementation

def bold_words_brute_force(string, words):
    string_length = len(string)
    bold_mask = [False] * string_length

    # Iterate through each starting position in the string
    for starting_position in range(string_length):
        # Check each word in our dictionary
        for word in words:
            if string[starting_position:].startswith(word):

                # Mark the substring to be bolded
                for i in range(len(word)):
                    bold_mask[starting_position + i] = True

    result = ""
    bold = False
    for i in range(string_length):
        if bold_mask[i] and not bold:
            result += "<b>"
            bold = True
        elif not bold_mask[i] and bold:

            # Close the bold tag when needed
            result += "</b>"
            bold = False
        result += string[i]

    if bold:
        result += "</b>"

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, imagine marking positions in the main string that should be bolded. Think of it like using a highlighter to mark the start and end of each word to be bolded.
For each of the words we want to bold, find all places where that word shows up in the main string.
For each occurrence, mark the start and end positions of that word in the main string as needing to be bolded. If any bold sections overlap, merge them into a single, larger bold section.
Now, go through the main string, and whenever you encounter a marked start position, insert a bold start tag. When you encounter a marked end position, insert a bold end tag.
Finally, combine the original characters of the main string and the bold tags to construct the final output string.

Code Implementation

def bold_words_in_string(string_to_bold, words_to_bold):
    string_length = len(string_to_bold)
    bold_marker = [False] * string_length

    for word in words_to_bold:
        for index in range(string_length - len(word) + 1):
            if string_to_bold[index:index + len(word)] == word:
                # Mark the positions to be bolded
                for marker_index in range(index, index + len(word)): 
                    bold_marker[marker_index] = True

    merged_markers = []
    start_index = -1

    for index, should_bold in enumerate(bold_marker):
        if should_bold and start_index == -1:
            start_index = index
        elif not should_bold and start_index != -1:
            merged_markers.append((start_index, index))
            start_index = -1

    if start_index != -1:
        merged_markers.append((start_index, string_length))

    result = ""
    marker_index = 0

    for index in range(string_length):
        if marker_index < len(merged_markers) and index == merged_markers[marker_index][0]:
            # Insert bold tag at the start
            result += "<b>"
        result += string_to_bold[index]
        if marker_index < len(merged_markers) and index == merged_markers[marker_index][1] - 1:
            # Insert closing bold tag at the end
            result += "</b>"
            marker_index += 1

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
words array is empty	Return the original string since there are no words to bold.
s is empty	Return an empty string, as there's nothing to bold in an empty string.
s is null or words is null	Throw IllegalArgumentException to indicate invalid input.
words contains an empty string	Treat the empty string as matching anything, resulting in the entire string 's' being bolded.
words contains duplicates	The algorithm should still function correctly, potentially increasing the number of bolded sections if overlaps exist.
words contains overlapping matches in s	The solution must correctly merge overlapping bolded sections into single, larger bolded sections.
s is very long and words is very large, potentially exceeding memory limits or causing a timeout.	The chosen algorithm (e.g., using boolean array marking) must have reasonable time and space complexity (ideally O(n*m) where n is len(s) and m is the total length of all words).
No word in 'words' exists in 's'	Return the original string 's' unmodified, as there are no words to bold.

words array is empty

How to Handle:

Return the original string since there are no words to bold.

s is empty

How to Handle:

Return an empty string, as there's nothing to bold in an empty string.

s is null or words is null

How to Handle:

Throw IllegalArgumentException to indicate invalid input.

words contains an empty string

How to Handle:

Treat the empty string as matching anything, resulting in the entire string 's' being bolded.

words contains duplicates

How to Handle:

The algorithm should still function correctly, potentially increasing the number of bolded sections if overlaps exist.

words contains overlapping matches in s

How to Handle:

The solution must correctly merge overlapping bolded sections into single, larger bolded sections.

s is very long and words is very large, potentially exceeding memory limits or causing a timeout.

How to Handle:

The chosen algorithm (e.g., using boolean array marking) must have reasonable time and space complexity (ideally O(n*m) where n is len(s) and m is the total length of all words).

No word in 'words' exists in 's'

How to Handle:

Return the original string 's' unmodified, as there are no words to bold.