Bold Words in String - Practice Coding Problems

Bold Words in String - Problem

Given an array of keywords words and a string s, make all appearances of all keywords words[i] in s bold.

Any letters between  and  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.

Input & Output

Example 1 — Basic Overlapping

$ Input: words = ["ab", "bc"], s = "abcabc"

› Output: "abcabc"

💡 Note: "ab" matches at positions [0,2) and [3,5). "bc" matches at [1,3) and [4,6). Overlapping intervals [0,2) and [1,3) merge to [0,3), and [3,5) and [4,6) merge to [3,6).

Example 2 — No Overlapping

$ Input: words = ["ab", "cd"], s = "abcd"

› Output: "abcd"

💡 Note: "ab" matches at [0,2) and "cd" matches at [2,4). No overlap, so each gets separate bold tags.

Example 3 — Complete Coverage

$ Input: words = ["abc"], s = "abc"

› Output: "abc"

💡 Note: Single keyword covers entire string, resulting in one bold region.

Constraints

1 ≤ words.length ≤ 1000
1 ≤ words[i].length ≤ 1000
words[i] consists of lowercase English letters only
1 ≤ s.length ≤ 1000
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Array of keywords and target string

Process

Find all keyword matches and merge overlapping regions

Output

String with minimal bold tags around merged regions

Key Takeaway

🎯 Key Insight: Merge overlapping bold regions to use the minimum number of bold tags while covering all keyword matches.

Asked in

G Google 25 a Amazon 18 M Microsoft 12

The key insight is to merge overlapping bold regions to minimize tag count. The optimal approach uses interval merging - find all keyword positions as intervals, merge overlapping ones, then add bold tags. Time: O(n*m*k + I log I), Space: O(I + n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Mark Each Keyword	O(n * m * k)	O(n)	Find each keyword individually and mark bold positions, then build result string
Interval Merging Approach	O(n * m * k + I log I)	O(I + n)	Find all keyword positions as intervals, merge overlapping intervals, then add bold tags

Brute Force - Mark Each Keyword — Algorithm Steps

Step 1: Create boolean array to track bold positions
Step 2: For each keyword, find all occurrences and mark positions as bold
Step 3: Build result string by adding and tags around bold regions

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create boolean array to track bold positions

Mark Keywords

For each keyword, find all occurrences and mark positions

Build Result

Add bold tags around marked regions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

char* solution(char words[][100], int wordsSize, char* s) {
    int n = strlen(s);
    if (n == 0 || wordsSize == 0) {
        char* result = malloc(n + 1);
        strcpy(result, s);
        return result;
    }
    
    bool* bold = calloc(n, sizeof(bool));
    
    // Mark all positions that should be bold
    for (int w = 0; w < wordsSize; w++) {
        int wordLen = strlen(words[w]);
        for (int i = 0; i <= n - wordLen; i++) {
            if (strncmp(s + i, words[w], wordLen) == 0) {
                for (int j = i; j < i + wordLen; j++) {
                    bold[j] = true;
                }
            }
        }
    }
    
    // Build result string
    char* result = malloc(n * 10); // Extra space for tags
    int pos = 0;
    int i = 0;
    
    while (i < n) {
        if (bold[i]) {
            strcpy(result + pos, "<b>");
            pos += 3;
            while (i < n && bold[i]) {
                result[pos++] = s[i++];
            }
            strcpy(result + pos, "</b>");
            pos += 4;
        } else {
            result[pos++] = s[i++];
        }
    }
    result[pos] = '\0';
    
    free(bold);
    return result;
}

int main() {
    char words[100][100];
    char s[1000];
    int wordsSize = 0;
    
    // Simple parsing - assumes format ["word1","word2"]
    char line[1000];
    fgets(line, sizeof(line), stdin);
    // Parse words manually
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(words, wordsSize, s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n * m * k)

n = string length, m = number of words, k = average word length. For each word, we scan the entire string

✓ Linear Growth

Space Complexity

O(n)

Boolean array to track bold positions plus result string

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Mark Each Keyword — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler